[Gold IV] 불 - 5427
성능 요약
메모리: 85684 KB, 시간: 1796 ms
분류
너비 우선 탐색, 그래프 이론, 그래프 탐색
제출 일자
2023년 12월 6일 13:46:22
문제 설명
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.
매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
- '.': 빈 공간
- '#': 벽
- '@': 상근이의 시작 위치
- '*': 불
각 지도에 @의 개수는 하나이다.
출력
각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.
💡 Solutions
📄 불.py
import sys
from collections import deque
def bfs(j, f):
que = deque()
for fire in f:
que.append((fire[0],fire[1], 0, '*'))
is_travel[fire[0]][fire[1]] = True
que.append((j[0],j[1], 0, '@'))
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 == '@' 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] == '*' or matrix[nx][ny] == '#' : continue
is_travel[nx][ny] = True
que.append((nx, ny, depth + 1, type))
return 'IMPOSSIBLE'
T = int(sys.stdin.readline())
for t in range(T):
M, N = 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)]
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] == '@':
jihon = (i, j)
if matrix[i][j] == '*':
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)