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

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

4179번: 불!

 

문제 해석

 

지훈이가 불을 피해 주어진 맵 밖으로 나가야한다.

맵에는 벽(#), 지훈이의 위치, 불의 위치가 주어진다.

지훈이는 상하좌우로 움직일 수 있다.

불은 상하좌우로 번지고, 벽으로는 번질 수 없다.

지훈이가 탈출하는 가장 빠른 시간을 출력하는 문제이다.

---

코드

 

from collections import deque

# input
input = __import__('sys').stdin.readline
arr = []
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
fire = deque()
n, m = map(int, input().split())
for i in range(n):
    arr.append(list(input().strip()))
    for j in range(m):
        if arr[i][j] == 'J':
            arr[i][j] = '.'
            start = (i, j)
        elif arr[i][j] == 'F':
            fire.append((i, j))

def solve():
    i, j = start
    visit = [[0] * m for _ in range(n)]
    q = deque()
    q.append((i, j))
    visit[i][j] = 1
    ans = 0
    while q:
        # 한 사이클씩 진행
        for _ in range(len(q)):
            i, j = q.popleft()
            for k in range(4):
                x, y = i + dx[k], j + dy[k]
                
                # 탈출한 경우
                if not(0 <= x < n and 0 <= y < m):
                    return ans + 1
                if arr[x][y] == '.' and visit[x][y] == 0:
                    
                    # 이동 후 불에 번질 경우 예외처리
                    flag = 1
                    for k in range(4):
                        cx, cy = x + dx[k], y + dy[k]
                        if not(0 <= cx < n and 0 <= cy < m): continue
                        if arr[cx][cy] == 'F': flag = 0
                        
                    # 이동 가능할 경우만 이동 (불에 안번질 때)
                    if flag:
                        visit[x][y] = 1
                        q.append((x, y))
        
        # 한 사이클 탐색 후 불 번지기
        for _ in range(len(fire)):
            i, j = fire.popleft()
            for k in range(4):
                x, y = i + dx[k], j + dy[k]
                if not(0 <= x < n and 0 <= y < m): continue
                if arr[x][y] == '.':
                    fire.append((x, y))
                    arr[x][y] = 'F'
            
        ans += 1
    return "IMPOSSIBLE"

print(solve())

---

문제 풀이

 

map을 입력 받을 때 불의 좌표는 따로 큐에 담아주었다. 지훈이의 시작 위치또한 따로 저장한 뒤 해당 위치는 빈 공간으로 만들어 주었다.

 

이 문제 또한 턴을 나누어 해결하는 문제이다.

따라서 q에 존재하는 만큼 반복하여 지훈이의 이동 경로를 탐색한 뒤 불을 번지도록 해주었다.

 

지훈이는 빈공간이고, 방문하지 않은 곳에 이동할 수 있다. 추가적인 예외로 불이 번질 경로를 예상하여 해당 지점 또한 갈 수 없도록 구현해 주어야 한다.

 

이후 불이 번지도록 해준다. 처음에는 불의 위치를 모두 찾아 해당 불을 기준으로 상하좌우에 존재하는 빈 공간의 좌표를 저장한 뒤, 불을 번지도록 구현했는데 시간초과와 틀렸다.

해결 방법으로 처음부터 불의 좌표를 따로 큐에 넣고, 해당 큐에서 BFS 탐색을 통해 번지도록 해주었다.