[🥇4 / 백준 4179 / 파이썬] 불!

 

4179번: 불!

 

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

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

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

출력

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

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 

 

예제 입력 4 4 #### #JF# #..# #..#

예제 출력 3

 

풀이

 

J의 이동과 F의 퍼짐을 시뮬레이션 + BFS로 구현하는 문제이다.

한 틱에 큐의 모든 원소를 비워가며, 모든 이동을 완료해야 하는 것을 주의해야 한다.

또한, J의 이동보다 불의 이동을 먼저 처리해주어야 한다.

 

다음 테스트 케이스를 참고하길 바란다.

 

예제 입력 4 4 #### #J.# #.F# #..#

예제 입력 IMPOSSIBLE

 

from collections import deque
import sys
input = sys.stdin.readline
sys.stdin = open("pyt.txt","r")

def main():
    n,m = map(int,input().split())
    board = [list(input().rstrip()) for _ in range(n)]
    move = [(0,1),(1,0),(0,-1),(-1,0)]
    J,F = deque(),deque()
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'J':
                J.append((i,j))
            elif board[i][j] == 'F':
                F.append((i,j))

    t = 0
    while J:
        t+=1
        tmp_J, tmp_F = set(),set()
        while F:
            x,y = F.popleft()
            for a,b in move:
                dx=x+a; dy=y+b
                if n>dx>=0 and m>dy>=0:
                    if board[dx][dy] in ['J','.']:
                        board[dx][dy] = 'F'
                        tmp_F.add((dx,dy))

        while J:
            x,y = J.popleft()
            for a,b in move:
                dx=x+a; dy=y+b
                if n>dx>=0 and m>dy>=0:
                    if board[dx][dy] == '.':
                        board[dx][dy] = 'J'
                        tmp_J.add((dx,dy))
                else:
                    print(t)
                    sys.exit()

        J = deque(tmp_J)
        F = deque(tmp_F)
    print('IMPOSSIBLE')
if __name__ == "__main__":
    main()