[백준 4179번] 파이썬 - 불!

백준 4179 - 불!

시간 제한 1초, 메모리 제한 256MB

# 조건

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

입력

• 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다.
  • 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
• 다음 입력으로 R줄 동안 각각의 미로 행이 주어진다.
• 각각의 문자들은 다음을 뜻한다.
  • #: 벽
  • .: 지나갈 수 있는 공간
  • J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
  • F: 불이 난 공간
• J는 입력에서 하나만 주어진다.

출력

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

# 접근 방법

• 우선, 지훈이와 불이 매 분 확산되기 때문에 불을 먼저 확산을 시켜주는 것이 지훈이가 안전한 곳으로 이동할 수 있는 방법이다.
  • 지훈이를 먼저 이동시키고 불을 확산시키면 가지 못하는 곳을 더 탐색하므로 비효율적이다.
• 따라서, 지훈이와 불을 deque에 담아준 후 지훈이가 갈 수 있는 곳이 없을 때 까지 탐색해준다.
• 불을 확산시키기 위해 현재 탐색할 불의 개수를 반환해주고 can_fire 함수로 불이 확산 가능한 곳을 저장해준다.
  • 위의 함수가 끝난 뒤 최초 불의 개수만큼 popleft 해준 후, 새로운 불 위치를 저장해준다.
• 지훈이도 마찬가지로 갈 수 있는 곳을 저장, 현재 위치 개수를 반환해준 후 위와 같은 로직으로 탐색하면 된다.
  • 다만 지훈이의 현재 위치가 탈출 가능한 곳이라면 탈출 시킨 후 exit() 을 통해 종료시켜주고
  • 지훈이가 새로 갈 수 있는 곳이 없다면 - j_val 리스트가 비어있다면 - IMPOSSIBLE 을 출력해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def can_fire(i, j):  
    for d in range(4):  
        ni, nj = i + di[d], j + dj[d]  
        if 0<=ni<N and 0<=nj<M and arr[ni][nj] == '.':  
            arr[ni][nj] = 'F'  
            f_val.append((ni, nj))  

def can_jihoon(i, j):  
    for d in range(4):  
        ni, nj = i + di[d], j + dj[d]  
        if 0<=ni<N and 0<=nj<M and arr[ni][nj] == '.' and not visited[ni][nj]:  
            visited[ni][nj] = True  
            j_val.append((ni, nj))  

N, M = map(int, input().split())  
arr = [[*map(str, input().rstrip())] for _ in range(N)]  

# 불과 지훈이 위치 저장  
jihoon, fire = deque(), deque()  
for i in range(N):  
    for j in range(M):  
        if arr[i][j] == 'J':  
            jihoon.append((i, j))  
            arr[i][j] = '.'  
        elif arr[i][j] == 'F':  
            fire.append((i, j))  


di, dj = [1, -1, 0, 0], [0, 0, 1, -1]  
# 불 확산 후 지훈이가 이동가능한 위치 저장해주기  
# 지훈이 방문 기록  
visited = [[False] * M for _ in range(N)]  
result = 0  
while jihoon:  
    # 불 먼저 확산시켜주기  
    # 현재 저장된 불의 개수    
    f_cnt = len(fire)  
    f_val = []  
    for i, j in fire:  
        can_fire(i, j)  
    if f_val:  
        for k in f_val:  
            fire.append(k)  
        for _ in range(f_cnt):  
            fire.popleft()  

    # 지훈이 현재 갈 수 있는 위치 개수  
    j_cnt = len(jihoon)  
    j_val = []  
    for i, j in jihoon:  
        # 탈출 가능한 곳이면 탈출  
        if i == 0 or i == N-1 or j == 0 or j == M-1:  
            print(result+1)  
            exit()  
        can_jihoon(i, j)  
    if j_val:  
        for k in j_val:  
            jihoon.append(k)  
        for _ in range(j_cnt):  
            jihoon.popleft()  
    else:  
        print('IMPOSSIBLE')  
        break  
    result += 1