아이템 줍기

from collections import deque

maps = [[False for _ in range(102)] for _ in range(102)]
visited = [[False for _ in range(102)] for _ in range(102)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

def bfs(startX, startY, targetX, targetY):
    q = deque()
    q.append([startX, startY, 0])
    visited[startX][startY] = True
    
    while q:
        cx, cy, cnt = q.popleft()
        
        for dxx, dyy in zip(dx, dy):
            nx, ny = cx+dxx, cy+dyy
            if nx == targetX and ny == targetY:
                return cnt+1
            
            if 0 <= nx < 102 and 0 <= ny < 102:
                if visited[nx][ny] or maps[nx][ny] == False:
                    continue
                visited[nx][ny] = True
                q.append([nx, ny, cnt+1])
                
    

def solution(rectangle, characterX, characterY, itemX, itemY):
    global maps
    
    for item in rectangle:
        # 꼬불한 경로 최단거리 오해 -> 2배로 확대
        lx, ly, ux, uy = item[0]*2, item[1]*2, item[2]*2, item[3]*2
        
        # 테두리 색칠
        for i in range(lx, ux+1):
            maps[ly][i] = True
            maps[uy][i] = True
        for j in range(ly, uy+1):
            maps[j][lx] = True
            maps[j][ux] = True

    # 내부 공백으로 다시 색칠
    for item in rectangle:
        lx, ly, ux, uy = item[0]*2, item[1]*2, item[2]*2, item[3]*2
        for i in range(lx+1, ux):
            for j in range(ly+1, uy):
                maps[j][i] = False

    # BFS로 따라가면서 탐색
    return bfs(characterY*2, characterX*2, itemY*2, itemX*2) // 2

LV3

아이디어가 중요한 문제였다.
처음에는 문제를 읽고 어떻게 풀어야 될지 감이 안잡혔다.

우선 직사각형의 좌표 정보만을 받아서 겹치는 부분을 어떻게 표현할지, 그리고 둘레 정보만을 어떻게 뽑아낼지 애매했다.

그러다가 문득 든 생각은 점의 좌표를 칸으로 생각해서 직사각형이 존재하는 위치에 1, 없는 위치에 0을 저장해두면 경로를 알 수 있겠다는 것이었다.

그리고 테두리를 제외한 내부의 경우 다시 0으로 초기화 해줘서 겹치는 둘레를 지워주면 되는 일이었다.

하지만 여기서 문제가 하나 있었다.
만약 ㄹ 구조처럼 꼬불한 경로를 따라가야되면 따로 방향이 저장돼있는 것이 아니기 때문에 bfs로 탐색할 때 당연히 더 최단거리로 가로질러 가지 않을까? 하는 문제였다.

그래서 받은 좌표를 2배씩 해주어 확대해 저장해주었다.
그렇게 되면 ㄹ처럼 꼬불한 구조도 가운데에 칸이 생겨 길이 구분될 수 있다.

마지막으로 bfs 탐색을 돌려 가장 최단길이를 리턴해주면 된다.

출처: https://school.programmers.co.kr/learn/courses/30/lessons/87694