[BOJ] 5427 불 (Python3)

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

’.’: 빈 공간
‘#’: 벽
‘@’: 상근이의 시작 위치
‘*’: 불
각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 “IMPOSSIBLE”을 출력한다.

정답 코드

from collections import deque


t = int(input())

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

for _ in range(t):
    isImpossible = True
    answer = 0
    n, m = map(int, input().split())
    
    graph = []
    q = deque() 
    
    for _ in range(m):
        graph.append(list(input()))
         
    for i in range(m):
        for j in range(n):
            if graph[i][j] == '*':
                q.append((i, j))
                
    for i in range(m):
        for j in range(n):
            if graph[i][j] == '@':
                graph[i][j] = 0
                q.append((i, j))
    
    while q:
        x, y = q.popleft()
        
        if graph[x][y] == '*':
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                if 0 <= nx < m and 0 <= ny < n:
                    if graph[nx][ny] == '.':
                        graph[nx][ny] = '*'
                        q.append((nx, ny))
                        
        if type(graph[x][y]) == int:
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                if 0 <= nx < m and 0 <= ny < n:
                    if graph[nx][ny] == '.':
                        graph[nx][ny] = graph[x][y] + 1
                        q.append((nx, ny))
                else:
                    print(graph[x][y] + 1)
                    q = deque()
                    isImpossible = False
                    break
    if isImpossible:
        print('IMPOSSIBLE')

문제 풀이

간만에 DFS 문제가 나왔다.

조건에 맞추어 불과 상근이를 옮겨주어야하는데, 중요한것은 불이 옮겨질 자리에는 상근이가 이동할 수 없기 때문에 반드시 불을 먼저 이동해주어야 한다.

큐를 두개 사용할수도 있겠지만 어차피 불을 먼저 큐에 넣으면 자동으로 불, 상근이, 불, 상근이 순으로 이동되므로 하나의 큐로 답을 구할 수 있다.

DFS의 개념만 알고있다면 아주 쉽게 풀 수 있는 문제다.