문제 링크

• https://www.acmicpc.net/problem/4179

문제 설명

• board에 지훈이의 위치 1개와 불의 위치 ?개가 주어진다

• 불은 인접한 빈 칸으로 한 칸씩 번진다

• 지훈이도 한 칸씩 움직인다

• 지훈이가 탈출할 수 있으면 최소 시간 출력

• 탈출할 수 없으면 IMPOSSIBLE 출력

풀이

• 지훈이의 위치에서 BFS로 모든 거리를 구한다

• 불의 위치에서 BFS로 모든 거리를 구한다

• board를 가장자리를 탐색하며 빈 칸일 경우 검사

• 지훈이의 거리 < 불의 거리일 경우 최소 거리 갱신

느낀 점

• 처음에는 BFS를 동시에 진행하면서 불이 있는 곳으로는 지훈이가 가지 않는 방식으로 해볼까 했는데

• 어려울 것 같아서 거리 리스트를 두 개 만들어서 모든 거리를 저장했다

• 그런데 다시 생각해보니 불에 대해 BFS를 먼저 하고

• 지훈이에 대해 BFS를 할 때 거리가 더 짧은 곳은 가지 않으면 될 것 같다

• 근데 지금 코드도 Python3로 통과가 돼서 패스

• 유형이 그래도 좀 익숙해진 것 같다.

코드

import sys
from collections import deque


def init():
    ipt = sys.stdin.readline
    r, c = map(int, ipt().split())
    board = []
    jihun = [-1, -1]
    fire_list = []
    for y in range(r):
        board.append(list(ipt().rstrip()))
        for x in range(c):
            if board[y][x] == 'J':
                jihun = (y, x)
                board[y][x] = '.'
            elif board[y][x] == 'F':
                fire_list.append((y, x))
                board[y][x] = '.'
    dy = [1,-1,0,0]
    dx = [0,0,1,-1]
    return r, c, board, jihun, fire_list, float('inf'), dy, dx


def bfs(start_list):
    dist_list = [[float('inf')] * c for _ in range(r)]
    visited = [[False] * c for _ in range(r)]
    q = deque()
    for start in start_list:
        sy, sx = start
        visited[sy][sx] = True
        dist_list[sy][sx] = 0
        q.append((sy, sx))
    while q:
        cy, cx = q.popleft()
        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if 0 <= ny < r and 0 <= nx < c:
                if not visited[ny][nx] and board[ny][nx] == '.':
                    visited[ny][nx] = True
                    q.append((ny, nx))
                    dist_list[ny][nx] = dist_list[cy][cx] + 1
    return dist_list


r, c, board, jihun, fire_list, min_dist, dy, dx = init()
jihun_dist = bfs([jihun])
fire_dist = bfs(fire_list)
for y in range(r):
    for x in range(c):
        if y == 0 or y == r-1 or x == 0 or x == c-1:
            if jihun_dist[y][x] < fire_dist[y][x]:
                min_dist = min(min_dist, jihun_dist[y][x])
if min_dist == float('inf'):
    print('IMPOSSIBLE')
else:
    print(min_dist + 1)