[BOJ][🟡4][백준#004179] 불!

문제 출처

BAEKJOON Online Judge #04179

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다.  불은 각 지점에서 네 방향으로 확산된다.  지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.  지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다.  각각의 문자들은 다음을 뜻한다.

#: 벽 .: 지나갈 수 있는 공간 J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간) F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다. 지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 

예제

입력

4 4
####
#JF#
#..#
#..#

출력

3

My Sol

import sys
input = sys.stdin.readline

# 지훈, 불 위치 찾기
def find_JF():
    global mat, I, J
    for i in range(I):
        for j in range(J):
            if mat[i][j] == 'F':
                F_set.add((i, j))
            elif mat[i][j] == 'J':
                J_set.add((i, j))

# 지훈 이동
def move_JH():
    global mat, I, J, J_set
    tmp = set()
    while J_set:
        ni, nj = J_set.pop()
        for di, dj in ((-1,0),(1,0),(0,-1),(0,1)):
            si, sj = ni+di, nj+dj
            if not (0<=si<I and 0<=sj<J): return True
            if mat[si][sj] == '.':
                mat[si][sj] = 'J'
                tmp.add((si, sj))
    J_set = tmp

def move_fire():
    global mat, I, J, F_set, J_set
    tmp = set()
    while F_set:
        ni, nj = F_set.pop()
        for di, dj in ((-1,0),(1,0),(0,-1),(0,1)):
            si, sj = ni+di, nj+dj
            if not (0<=si<I and 0<=sj<J): continue
            if mat[si][sj] == '#': continue
            if mat[si][sj] == 'F': continue
            mat[si][sj] = 'F'
            J_set -= {(si, sj)}
            tmp.add((si, sj))
    F_set = tmp

I, J = map(int, input().split())
mat = [list(input()) for _ in range(I)]
J_set, F_set = set(), set()
find_JF()

time = 0
impossible = 0
while True:
    time += 1
    if move_JH(): break
    move_fire()
    if not J_set:
        impossible = 1
        break

print('IMPOSSIBLE') if impossible else print(time)

골드4 치고는 간단한 문제였다.

1. 입력을 처리한다. 지훈이와 불의 위치를 각각의 set에 tuple로 담아준다.
2. 지훈이가 먼저 이동한다. set에 있는 지훈이의 좌표에서 가능한 모든 상하좌우의 이동을 한다. 벽과 불쪽은 이동하지 않고, 만약 범위를 벗어난다면 바로 True를 반환한다. 이동할 수 있는 모든 좌표는 tmp에 넣은 뒤, 모든 가능한 이동을 mat에 표시했다면 J_set에 tmp를 할당한다.
3. 지훈이가 이동한 뒤, 불이 이동하는데, 벽 또는 좌표를 벗어난 구역만 아니라면 mat에 모두 F를 표시하고 F_set에 좌표를 추가한다. 여기서 J_set에 해당하는 좌표가 있다면 빼내어준다. 즉, 이미 지훈이가 이번에 이동한 좌표에 불이 옮겨갔다면 지훈이는 살 수 없으므로 해당하는 좌표는 빼주는 것이다.
4. 이렇게 지훈이의 이동에서 True가 반환될 때까지 반복하는데, 만약 불길이 거세서 지훈이가 이동 후 살아남을 수 있는 경우가 없다면 J_set은 비게 되므로 False를 판단하여 impossible 변수를 1로 체크한 뒤 while문을 종료한다.
5. impossible 변수의 T/F 여부에 따라 time 또는 IMPOSSIBLE을 출력한다.

결과

맞았습니다!!