[백준 4179] 불!

 

4179번: 불!

 

알고리즘 : BFS

난이도 : 골드Ⅳ

 

1. 문제요약

• 2차원 맵이 주어진다. '#'은 벽을, '.'은 빈 공간을 나타낸다. 또한 'J'는 사람을, 'F'는 불을 나타낸다.
• 매 시간 불은 사방으로 퍼지고, 사람 또한 사방으로 이동할 수 있다.
• 이때 사람이 불을 피해 맵에서 탈출할 수 있는 최단시간을 출력해야 한다. 탈출이 불가능할 경우 IMPOSSIBLE을 출력한다.

2. 구현과정

• BFS 문제로 앞서 풀었던 불 문제와 거의 동일한 문제이다.
• 일단 불과 사람의 이동로직을 간단히 하고 탈출조건을 명확히 파악하기 위해 '!'로 맵을 패딩해 주었다.
• 맵을 따라 이동하는 것이 두 가지라는 점이 특이사항인데, 매 시간마다 불을 먼저 확산시킨 뒤에 사람을 이동시켜가며 탈출하는 과정을 구현해나간다.

3. 파이썬 코드

from collections import deque
import sys

input = lambda: sys.stdin.readline().rstrip()

r, c = map(int, input().split())

# 맵초기화 : '!'으로 패딩
field = [['!'] * (c + 2)]
for _ in range(r):
    field.append(['!'] + list(input()) + ['!'])
field.append(['!'] * (c + 2))

# 불, 사람 각각 큐 구현 / 처음좌표 찾기
fire, human = deque(), deque()
for i in range(r + 2):
    for j in range(c + 2):
        if field[i][j] == 'F':
            fire.append([i, j])
        if field[i][j] == 'J':
            human.append([i, j, 0])

# 이동방향
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# bfs 수행 : 불을 상하좌우로 확산시킨 후 사람의 이동방향 탐색
answer = False
while human:
    # 불 확산
    tmp = deque()
    while fire:
        xfire, yfire = fire.popleft()
        for i in range(4):
            nxfire, nyfire = xfire + dx[i], yfire + dy[i]
            if field[nxfire][nyfire] in '.J':  # 불이 확산가능한 곳
                tmp.append([nxfire, nyfire])
                field[nxfire][nyfire] = 'F'  # 불 확산된 곳 갱신
    fire = tmp
    # 사람 이동방향 탐색
    tmp2 = deque()
    while human:
        xman, yman, tman = human.popleft()
        for i in range(4):
            nxman, nyman, ntman = xman + dx[i], yman + dy[i], tman + 1
            if field[nxman][nyman] == '!':  # 탈출성공
                answer = ntman
            if field[nxman][nyman] == '.':
                tmp2.append([nxman, nyman, ntman])
                field[nxman][nyman] = 'J'  # 사람이 이동한 곳 갱신
    human = tmp2
    # while문 탈출조건
    if answer:
        print(answer)
        break
else:
    print('IMPOSSIBLE')