4179. 불！

업데이트 시간 : 2023-12-05 05:32:10 +0000

[Gold IV] 불! - 4179

문제 링크

성능 요약

메모리: 178892 KB, 시간: 604 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2023년 12월 5일 14:31:57

문제 설명

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

💡 Solutions

📄 불！.py

import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
matrix = [list(map(str,sys.stdin.readline())) for _ in range(N)]

d = [(0,1),(0,-1),(1,0),(-1,0)]

def bfs(j, f):

    que = deque()
    
    for fire in f:
        que.append((fire[0],fire[1], 0, 'F'))
        is_travel[fire[0]][fire[1]] = True

    que.append((j[0],j[1], 0, 'J'))
    is_travel[j[0]][j[1]] = True
    

    while que:
        x, y, depth, type = que.popleft()

        for dx, dy in d:
            nx = x + dx
            ny = y + dy

            if nx < 0 or ny < 0 or nx >= N or ny >= M : continue
            if is_travel[nx][ny] : continue
            if type == 'J' and (nx == 0 or ny == 0 or nx == N-1 or ny == M-1) and matrix[nx][ny] == '.' : return depth + 2
            if matrix[nx][ny] == 'F' or matrix[nx][ny] == '#' : continue

            is_travel[nx][ny] = True
            que.append((nx, ny, depth + 1, type))

    return 'IMPOSSIBLE'


is_travel = [[False for _ in range(M)] for _ in range(N)]
jihon = None
fire = []
for i in range(N):
    for j in range(M):
        if matrix[i][j] == 'J':
            jihon = (i, j)
        if matrix[i][j] == 'F':
            fire.append((i,j))

if (jihon[0] == 0 or jihon[1] == 0 or jihon[0] == N-1 or jihon[1] == M-1):
    answer = 1
else:
    answer = bfs(jihon, fire)

print(answer)