[Python] 프로그래머스 / 아이템 줍기

문제 링크

 

이렇게 여러 개의 직사각형이 형성하는 영역의 외곽을 따라 이동하여 빨간 점에서 파란 점까지의 최소 거리를 찾으면 되는 문제.

 

이거 걍 BFS 아님?

정확하다. 이런 문제는 그냥 이렇게 격자를 나누어서

 

우리가 갈 수 있는 "도형의 외곽"을 1로 채우고, 도형의 내부는 2로 채워서

 

BFS 탐색하면 끝!

라고 생각하기 쉽다. 그런데 치명적인 문제점이 있다.

 

 

 

바로 저 보라색 부분이 문제된다. 원래는 아래와 같이 삥 돌아가야 하는 경로인데, 위와 같은 형태의 map이라면 바로 위로 뚫고 가버리니 말이다.

그러므로, 더 촘촘하게 격자를 나누어야 한다. (두배로)

 

자 이제 안심이다. 이제는 붙어있는 변과 한칸 띄어져 있는 변이 정확히 구분된다.

 

정답코드

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    
    world = [[0] * 102 for _ in range(102)]
    seen = [[False] * 102 for _ in range(102)]
    
    for x1, y1, x2, y2 in rectangle :
        x1, y1, x2, y2 = x1*2, y1*2, x2*2, y2*2
        
        for x in range(x1, x2+1) :
            for y in range(y1, y2+1) :
                if x1<x<x2 and y1<y<y2 :
                    world[x][y] = 2
                else :
                    if not world[x][y] :
                        world[x][y] = 1
                
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    queue = deque([[0, 2*characterX, 2*characterY]])
    
    while queue :
        distance, cx, cy = queue.popleft()
        
        if cx == 2*itemX and cy == 2*itemY :
            break
        
        if seen[cx][cy] :
            continue
        seen[cx][cy] = True
        
        for i in range(4) :
            nx = cx + dx[i]
            ny = cy + dy[i]
            
            if 0<=nx<102 and 0<=ny<102 and world[nx][ny] == 1 :
                queue.append([distance+1, nx, ny])
                
    return distance//2