프로그래머스 연습문제 아이템줍기

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/87694

접근

사각형을 하나씩 순회하면서 모서리 부분은 1, 안쪽 부분이거나 다른 사각형의 안쪽부분이라면 0으로 그래프 초기화

코드

from collections import deque
            

def solution(rectangle, characterX, characterY, itemX, itemY):
    
    leng=max(list(map(max, rectangle)))*2
    graph=[[5 for i in range(leng+1)] for j in range(leng+1)]
    visited=[[0 for i in range(leng+1)] for j in range(leng+1)]
    answer=10000
    movelist=[[1,0],[-1,0],[0,-1],[0,1]]
    for re in rectangle:
        re=list(map(lambda x:x*2,re))
        for i in range(re[1],re[3]+1):
            for j in range(re[0],re[2]+1):
                if graph[i][j]!=0 and (i==re[1] or i==re[3] or j==re[0] or j==re[2]):
                    graph[i][j]=1
                else:
                    graph[i][j]=0
    
    curx,cury=characterX*2, characterY*2
    visited[cury][curx]=1
    itemx,itemy=itemX*2, itemY*2
    queue=deque()
    queue.append([curx,cury,0])
    
    while queue:
        curx,cury,curd=queue.popleft()
        if curx==itemx and cury==itemy:
            answer=min(answer,curd//2)
        
        for mo in movelist:
            nx,ny=curx+mo[0],cury+mo[1]
            if 0<=nx<leng+1 and 0<=ny<leng+1 and visited[ny][nx]==0 and graph[ny][nx]==1:
                queue.append([nx,ny,curd+1])
                visited[ny][nx]=1
                
    return answer

참고

실제 문제의 좌표평면을 그래프상의 숫자 0과1로 옮길떄 주의해야 할 점은 다음과 같다

좌표평면의 ㄷ자 모양과 ㅁ자 모양을 그래프로 옮길 경우 두 그래프의 형태 모두
1 1
1 1
로 표현된다. 그렇기 떄문에 위와같은 문제를 해결할 떄는 그래프의 좌표를 2배로 늘려주는 방식 또한 고려해야한다. 만약 위 경우를 그래프를 두배로 늘렸을 경우로 표현한다면

1 1 1
0 0 1
0 0 0 과
1 1 1
1 1 1
1 1 1로 정상적으로 구별이 가능해진다.