[Python] 백준 31946: 죽음의 등굣길

 solved.ac기준 Silver 1

문제

입력

출력

지훈이가 살아서 등교에 성공할 수 있으면 ALIVE, 그렇지 않으면 DEAD를 출력한다.

예제 입력 1

2
3
0 0 0
0 0 0
1

예제 출력 1

ALIVE

예제 입력 2

2
2
0 0
0 1
5

예제 출력 2

DEAD

 

정답 코드

from collections import deque

N = int(input())
M = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
X = int(input())

visited = [[False] * M for _ in range(N)]
q = deque()
q.append((0, 0))
visited[0][0] = True

result = "DEAD"
color = arr[0][0]

while q:
    for _ in range(len(q)):
        x, y = q.popleft()
        
        if x == N-1 and y == M-1:
            q = []
            result = "ALIVE"
            break

        for dx in range(-X, X+1):
            for dy in range(-X, X+1):
                # 맨해튼 거리 이하일 때만 검사
                if abs(dx) + abs(dy) <= X:
                    new_x = x + dx
                    new_y = y + dy

                    if  0 <= new_x < N and 0 <= new_y < M and\
                        not visited[new_x][new_y] and\
                        arr[new_x][new_y] == color:
                        q.append((new_x, new_y))
                        visited[new_x][new_y] = True
                    
print(result)

 

 우선 일반적인 BFS로 구성한 뒤, 다음 노드로 이동할 때 맨해튼 거리를 쉽게 계산하도록 한다. 내가 갈 수 있는 최대 이동 칸 수는 가로 세로를 합하여 X이므로 이중 for문으로 이동 노드를 찾는 방식으로 했다. 

 탐색 도중 N행 M열에 도달하게 되면 결과를 ALIVE로 바꾸고 루프를 종료한다.