from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    m = [[0]*102 for i in range(102)]
    for i in rectangle :
        ax,ay,bx,by = i
        ax,ay,bx,by = 2*ax,2*ay,2*bx,2*by
        for j in range(ax, bx+1) :
            for k in range(ay, by + 1) :
                m[j][k] = 1
                
    for i in rectangle :
        ax,ay,bx,by = i
        ax,ay,bx,by = 2*ax,2*ay,2*bx,2*by
        for j in range(ax+1, bx) :
            for k in range(ay+1, by) :
                m[j][k] = 0
                
    queue = deque([[2* characterX, 2*characterY,0]])
    m[2*characterX][2*characterY] = 0
    point = [(-1, 0), (1,0), (0,1),(0,-1)]
    while queue :
        x,y,n = queue.popleft()
        answer = n
        if x == 2*itemX and y == 2*itemY : break
        for ix,iy in point :
            if m[x+ix][y+iy] == 1 : 
                m[x+ix][y+iy] = 0
                queue.append([x+ix,y+iy,n+1])
                
    return answer // 2

• 문제정리

  여러 직사각형이 겹쳐 있는 상태에서 합쳐진 직사각형들의 모서리를 따라 시작지점에서 목표지점까지가는 최단거리를 구하시오

• 풀이과정

  진짜 어떻게 풀지 모르겠어서 다른사람의 풀이를 찾아보았다.

  깊이/너비우선탐색 문제라는데 도저히 어떻게 풀지 고민이여서 찾아보았는데

  길찾는데에 깊이/너비우선탐색을 사용하였고 직사각형을 활용하여 경로를 찾기위해 아이디어를 찾는 것이였다. 처음부터 겁먹었던거같다.

  

  처음에 이거를 보고 왜 이렇게하지? 왜 안을 채우고 다시지우지 라는 생각을 했는데 그렇지 않으면 안쪽에 선이 남아서 채운 후 지워야했다. → 즉 위의 과정을 통해 경로를 생성하고 bfs를 하면되었는데

  계속 좌표에 2를 곱해야한다는 이야기가 있어 찾아보았더니

  

  ㄷ자를 컴퓨터는 좌료로 보기 때문에 bfs시 최단경로를

  (1,1)(2,1)(2,2)(2,1)로 보는 것이아니라 (1,1)(1,2)로 보는 것이였다.

  그래서 풀이는 좌표를 2배확대해서 우회하도록 풀이하고 있었다.

• 풀이 후

  거의 비슷하게 풀이한거 같다.

  다만 2배를 하지않고 중간값을 체크해서 풀이하는 사람도 있었다.