[프로그래머스] 아이템 줍기 (파이썬)

난이도 : LV 3

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

문제해결 아이디어

• 사각형의 테두리를 graph에 1로, 내부와 외부는 0 으로 표시한다.
• 단위가 1씩 되면 길이 없더라도 graph에서는 붙어있는 것처럼 표현되기 때문에 전부 길이를 2배로 늘려준다.
  • ex) 아래ㅐ 그림에서 3,5 와 3,6은 이어져있지 않지만 그래프내에서는 1이 연속해 있다.
    
• 그래프를 탐색하고 해당 이동거리에 // 2를 해준 값을 리턴

소스코드

from collections import deque

def solution(rectangle, chX, chY, itX, itY):
    dx, dy = [0,0,-1,1], [1,-1,0,0]
    # 테두리 그리기
    graph = [[-1] * 102 for _ in range(102)]
    for r in rectangle:
        x1,y1,x2,y2 = map(lambda x:x*2, r)  # 두배     
        for i in range(x1,x2+1):
            for j in range(y1, y2+1):
                if x1 < i < x2 and y1 < j < y2: #테두리 내부는 0
                    graph[i][j] = 0
                elif graph[i][j] != 0 : # 다른 사각형의 테두리 내부면 0
                    graph[i][j] = 1
        
    
    q = deque()
    q.append((2*chX,2*chY))    
    visited = [[0] * 101 for _ in range(101)]
    visited[2*chX][2*chY] = 1
    cnt = 0
    
    while q:
        cnt += 1
        for _ in range(len(q)):
            x,y = q.popleft()
            if x == 2*itX and y == 2*itY:
                return cnt//2
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if graph[nx][ny] == 1 and not visited[nx][ny]:
                    visited[nx][ny] = 1
                    q.append((nx,ny))