Algorithm/BOJ
[백준] 5427번 - 불 (파이썬)
_temp
2022. 2. 2. 15:17
# 불
from collections import deque
import sys
input = sys.stdin.readline
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def burn():
for _ in range(len(fire)):
x, y = fire.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < N and 0 <= ny < M:
if arr[nx][ny] != '#' and arr[nx][ny] != '*':
arr[nx][ny] = '*'
fire.append((nx, ny))
def move():
isgo = False
for _ in range(len(start)):
x, y = start.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < N and 0 <= ny < M:
if visited[nx][ny] == 0 and arr[nx][ny] != '#' and arr[nx][ny] != '*':
isgo = True
visited[nx][ny] = visited[x][y] + 1
start.append((nx, ny))
else:
return visited[x][y]
if not isgo:
return 'IMPOSSIBLE'
T = int(input())
for _ in range(T):
M, N = map(int, input().split())
arr = []
fire = deque()
start = deque()
for i in range(N):
arr.append(list(input().strip()))
for j in range(M):
if arr[i][j] == '*':
fire.append((i, j))
if arr[i][j] == '@':
start.append((i, j))
visited = [[0] * M for _ in range(N)]
visited[start[0][0]][start[0][1]] = 1
result = 0
while True:
burn()
result = move()
if result:
break
print(result)
BFS
1. 불길의 시작 위치와 출발위치를 각각 fire리스트와 start리스트에 append
2. result값이 return될 때까지 반복
- burn (불길이 번지는 함수) : 현재 불이 있는 위치의 상하좌우에 불이 번짐
- move (상근이가 이동하는 함수) : 현재 상근이가 있는 위치의 상하좌우로 이동
- 만약 범위 밖으로 이동한다면 return 이동시간
- 만약 이동이 없다면 return 'IMPOSSIBLE'
3. result 출력