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

https://www.acmicpc.net/problem/4179

 

불이야~

문제 설명

미로 속에서 지훈이가 화재로부터 도망쳐야 한다. 미로의 크기와 구성은 주어지며, 지훈이는 미로의 가장자리로 탈출해야 한다. 불(F)은 매 초마다 확산되며, 지훈이는 불보다 먼저 가장자리에 도착해야 탈출할 수 있다.

 

 

풀이

import sys
from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(check):
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < r and 0 <= ny < c:
        if maze[nx][ny] == '.'or maze[nx][ny] == 'J':
          if check == 'J':
            if dis_j[nx][ny] == -1:
              dis_j[nx][ny] = dis_j[x][y] + 1
              q.append((nx,ny))
          if check == 'F':
            if dis_f[nx][ny] == -1:
              dis_f[nx][ny] = dis_f[x][y] + 1
              q.append((nx,ny))
          

r, c = map(int, sys.stdin.readline().split())
maze = [list(map(str, list(sys.stdin.readline().strip()))) for _ in range(r)]
dis_j = [[-1 for _ in range(c)] for _ in range(r)]
dis_f = [[-1 for _ in range(c)] for _ in range(r)]
q = deque()
# J의 초기 위치 설정
for i in range(r):
  for j in range(c):
    if maze[i][j] == 'J':
      q.append((i,j))
      dis_j[i][j] = 0
bfs('J')
q = deque()
# F의 초기 위치 설정
for i in range(r):
  for j in range(c):
    if maze[i][j] == 'F':
      q.append((i,j))
      dis_f[i][j] = 0
bfs('F')

# 최단 시간 계산
min_time = float('inf')
for i in range(r):
    for j in range(c):
        if (i == 0 or i == r-1 or j == 0 or j == c-1) and dis_j[i][j] != -1:
            if dis_j[i][j] < dis_f[i][j] or dis_f[i][j] == -1:
                min_time = min(min_time, dis_j[i][j])
# 결과 출력                
if min_time == float('inf'):
    print("IMPOSSIBLE")
else:
    print(min_time + 1)

 

이 문제에서 유의할 점은 지훈이와 불이 동시에 움직인다는 것이다.

그래서 각 칸마다 지훈이의 이동시간, 불의 이동시간을 저장하는 2차원배열을 만들고

각 각 따로 bfs를 사용 하여 이동시간을 계산.

그 후 두 개의 배열의 가장자리 부분을 비교해서 지훈이가 불보다 더 빨리 도착하는 최소시간을 찾았다. 

 

 

 

float('inf')는 파이썬에서 양의 무한대를 나타내는 값

이걸 이용해서 최소값을 쉽게 구할 수 있었다.