오늘의 알고리즘 - boj-5427

문제

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

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

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

풀이

지난번 불! 문제와 비슷한 로직이다.

타입이라는 변수를 통해서 상근이가 움직인건지 아니면 불이 움직인건지 체크해서 상근이가 움직인 경우의수이고 현재 maze테이블의 끝에 닿았다면 (아래의 조건)

cur_row == 0 or cur_row == N-1 or cur_col == 0 or cur_col == M-1

라면 현재 visited값을 출력해주면 상근이가 빌딩을 탈출할 수 있는 이동횟수의 최솟값을 구할 수 있다.

그리고 break문을 탈출하지 않는 상황은 탈출 불가능한 상황이므로 else문을 통해서 impossible을 출력해준다.

from collections import deque
import sys

T = int(input())
directions = [[0, 1], [1, 0], [-1, 0], [0, -1]]

for _ in range(T):
    M, N = map(int, input().split())
    maze = [input() for _ in range(N)]
    
    visited = [[0] * M for _ in range(N)]
    
    route_queue = deque()
    
    for i in range(N):
        for j in range(M):
            if maze[i][j] == "*":
                route_queue.append((i,j, "*"))
                visited[i][j] = 1
                
    for i in range(N):
        for j in range(M):
            if maze[i][j] == "@":
                route_queue.append((i,j, "@"))
                visited[i][j] = 1
                
    while route_queue:
        
        cur_row, cur_col, type_ = route_queue.popleft()
        
        if type_ == "@" and (cur_row == 0 or cur_row == N-1 or cur_col == 0 or cur_col == M-1):
            print(visited[cur_row][cur_col])
            break
        
        for direction in directions:
            next_row = cur_row + direction[0]
            next_col = cur_col + direction[1]
            
            if 0 > next_row or next_row >= N or 0 > next_col or next_col >= M: continue 
            if visited[next_row][next_col]: continue
            if maze[next_row][next_col] == "#": continue
            
            visited[next_row][next_col] = visited[cur_row][cur_col] + 1
            route_queue.append((next_row, next_col, type_))
    else: print("IMPOSSIBLE")