4179번 불!

문제

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

접근 방식

BFS를 활용한 시뮬 문제

처음엔 하나의 큐에 지훈이 위치 먼저 넣고, 불들의 위치를 같이 넣고 시작했는데, 이렇게 하니 50% 쯤에서 틀렸다.

반례 :

	###
    #J.
    #.F
    

이런 케이스에서 지훈이가 탈출할 수 있기 때문!

불이 퍼지는 것과 지훈이 이동이 같이 수행되어야 하는데, 이걸 어떻게 할까 고민하다가, bfs를 두번 수행하는 방식으로 풀기로 했다.

불이 퍼지는 초들을 먼저 맵에 기록하고, 그 다음에 지훈이가 이동하는 곳에 기록된 불이 퍼진 시각이 지훈이의 시각보다 작다면 이동할 수 있도록 했다. 자료형 맞추기 위해 숫자 -> 스트링 형식으로 넣었는데 그냥 따로 배열 둬서 해도 됐을 듯. 맵 밖으로 탈출하는 게 목적이라, 경계값 신경 안 쓰도록 테두리를 'x'로 처리했다.

코드

import sys
from collections import deque

input = sys.stdin.readline

r, c = map(int, input().split())
board = [list(input()) for _ in range(r)]

# 지훈 위치 기록 + 불 위치 큐에 넣기
fq = deque([])

jx, jy = None, None
for i in range(r):
    for j in range(c):
        if board[i][j] == 'J':
            jx, jy = i + 1, j + 1
            board[i][j] = '.'
        elif board[i][j] == 'F':
            fq.append((i + 1, j + 1, 0))
            board[i][j] = '0'

# 테두리 'x' 처리
nboard = [['x'] * (c + 2) for _ in range(r + 2)]
for i in range(r):
    for j in range(c):
        nboard[i + 1][j + 1] = board[i][j]


def spread():  # 시간 만큼 불 위치 표시
    while fq:
        cx, cy, d = fq.popleft()

        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            if nboard[cx + dx][cy + dy] == '.':
                nboard[cx + dx][cy + dy] = str(d + 1)
                fq.append((cx + dx, cy + dy, d + 1))


def move():  # (현재 시간 <= 불 시간) -> 지훈 이동
    jq = deque([(jx, jy, 0)])

    visited = [[False] * (c + 2) for _ in range(r + 2)]
    visited[jx][jy] = True

    while jq:
        cx, cy, d = jq.popleft()

        if nboard[cx][cy] == 'x':
            return d

        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            if nboard[cx + dx][cy + dy] == '#':
                continue
            if (nboard[cx + dx][cy + dy] in {'.', 'x'} or d + 1 < int(nboard[cx + dx][cy + dy])) and not visited[cx + dx][cy + dy]:
                visited[cx + dx][cy + dy] = True
                jq.append((cx + dx, cy + dy, d + 1))

    return -1


spread()
res = move()

print("IMPOSSIBLE" if res == -1 else res)