[백준 5427번] 불

5427번: 불

# 상근이는 불이 옮겨진 칸과 불이 붙으려는 칸으로 이동 X
# 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

# 빌딩의 지도가 주어졌을때, 얼마나 빨리 빌딩을 탈출할 수 있는가(최단 시간)

# 빌딩을 탈출하는 최단 시간, 불가능하다면 IMPOSSIBLE 출력

from collections import deque

t = int(input())

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

for _ in range(t):
    w, h = map(int,input().split())

    # 빈공간(.), 벽(#), 시작위치(@), 불(*)
    area = [list(input()) for _ in range(h)]
    visited = [[0]*w for _ in range(h)]
    
    fire_list = []

    enable_set = set()

    def addEnable(x,y): # 불이 붙으려는 칸을 이동 불가능한 집합에 추가하는 함수
        for i in range(4):
            temp_x, temp_y = x + dx[i], y + dy[i]
            if 0 <= temp_x < h and 0 <= temp_y < w and area[temp_x][temp_y] == '.':
                enable_set.add((temp_x,temp_y))

    for i in range(h):
        for j in range(w):
            if area[i][j] == "@":
                start_x, start_y = i, j
            
            if area[i][j] == "*":
                fire_list.append((i,j))
                addEnable(i,j)

    def bfs():
    
        queue = deque([(start_x,start_y,'sang')] + [(x,y,"fire") for x,y in fire_list])

        while queue:
            
            x, y, value = queue.popleft()

            for i in range(4):
                temp_x = x + dx[i]
                temp_y = y + dy[i]

                if 0 <= temp_x < h and 0 <= temp_y < w:
                    if value == "sang":
                        if area[temp_x][temp_y] == '.' and visited[temp_x][temp_y] == 0  and (temp_x,temp_y) not in enable_set:
                            queue.append((temp_x,temp_y,'sang'))
                            visited[temp_x][temp_y] = visited[x][y] + 1
                    elif value == "fire":
                        if area[temp_x][temp_y] == '.':
                            queue.append((temp_x,temp_y,'fire'))
                            area[temp_x][temp_y] = "*"
                            addEnable(temp_x,temp_y)
                else:
                    if value == "sang":
                        print(visited[x][y]+1)
                        return
        
        print("IMPOSSIBLE")
        return
                
    bfs()

 

이번 문제는 상근이의 초기 위치와 불이 붙은 위치 좌표들이 주어졌을 때, 매초 상하좌우로 불이 번지고 상근이 또한 상하좌우로 움직일 수 있다(불이 붙었거나 불이 붙을 예정인 좌표는 이동 X)는 가정 하에, 2차원 건물 좌표에서 벗어나는 최단 시간을 구하는 문제이다.

 

먼저 최단 시간을 구하는 문제이고, 매초마다 상하좌우로 퍼져나가도록 구현하기 위해서는 근처에 있는 좌표들을 기준으로 탐색하는 BFS(너비 우선 탐색) 알고리즘이 필요하다고 판단했다.

 

또한 deque에서 pop할 때마다 해당 좌표에서 상하좌우로 이동하고자 하는 대상이 상근이(sang)인지, 불(fire)인지 구별하기 위해 (x좌표, y좌표, 대상)으로 deque에 저장해주었다.

enable_set = set()

def addEnable(x,y): # 불이 붙으려는 칸을 이동 불가능한 집합에 추가하는 함수
     for i in range(4):
         temp_x, temp_y = x + dx[i], y + dy[i]
         if 0 <= temp_x < h and 0 <= temp_y < w and area[temp_x][temp_y] == '.':
             enable_set.add((temp_x,temp_y))

 

여기서 가장 중요한 것은, 상근이가 불이 붙을 예정인 좌표로 이동할 수 없다는 것인데, 이를 위해서 불이 붙을 예정인 좌표, 즉 이동할 수 없는 좌표를 enable_set에 저장해주었다.(불의 좌표를 기준으로 이동불가능한 좌표를 추가해주는 addEnable 함수)

 

마지막으로 다음 좌표(temp_x, temp_y)가 주어진 건물 좌표에서 벗어나는 경우 탈출에 성공한 것이기 때문에 현재까지 '이동한 시간 + 1'을 출력하고 함수를 return 해주었고, 탈출하지 못하면 그대로 while문이 종료되면서 'IMPOSSIBLE'을 출력하게 되도록 하였다.

 

BFS를 복습할 수 있었던 좋은 문제였다 :)