[백준 4179번] 불!

4179번: 불!

from collections import deque
r,c = map(int,input().split())


maze = [list(input()) for _ in range(r)]
visited = [[-1]*c for _ in range(r)]

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

fire_list = []

for i in range(r):
    for j in range(c):
        if maze[i][j] == "J":
            start_x, start_y = i, j
        if maze[i][j] == "F":
            fire_list.append((i,j,"F"))

def bfs():
    visited[start_x][start_y] = 0

    for fire_x,fire_y,v in fire_list:
        visited[fire_x][fire_y] = 0
    
    queue = deque(fire_list+[(start_x,start_y,"J")])

    while queue:
        cur_x, cur_y, value = queue.popleft()

        for i in range(4):
            nx = cur_x + dx[i]
            ny = cur_y + dy[i]

            if (nx < 0 or nx >= r or ny < 0 or ny >= c) and value == "J":
                return visited[cur_x][cur_y] + 1
            
            if 0 <= nx < r and 0 <= ny < c and maze[nx][ny] == "." and visited[nx][ny] == -1:
                visited[nx][ny] = visited[cur_x][cur_y] + 1
                queue.append((nx,ny,value))

    return -1

result = bfs()

if result == -1:
    print("IMPOSSIBLE")
else:
    print(result)

이번 문제는 지훈이와 불이 붙은 위치에서 사방으로 이동할 수 있고, 미로의 가장자리에서 탈출할 수 있다는 가정하에, 지훈이가 탈출할 수 있는지 여부와 탈출할 수 있는 최단 시간을 구하는 문제이다.

 

지훈이가 움직이는 동시에 불도 같이 확산되기 때문에, 지훈이의 좌표와 불의 좌표를 동시에 queue에 담아준 뒤 BFS 알고리즘을 사용하여 이동시켜주었다.

 

그 후 지훈이의 좌표가 미로를 벗어날 경우(nx < 0 or nx >= r or ny < 0 or ny >= c)에 이동한 거리를 리턴해주었다. (BFS를 사용했기 때문에 최단 거리임이 보장됨)

 

그리고 단순히 x, y 좌표만 queue에 담아준다면 이동하는 대상이 지훈인지 불인지 알 수 없기 때문에 queue에 'J'나 'F'를 담아줌으로써 움직이는 대상을 구분해주었다.

 

여러 좌표에서 동시다발적으로 진행되는 BFS 알고리즘을 복습해볼 수 있는 좋은 문제였다 :)