[Python] 5427번 불

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

5427번: 불

---

 

22/11/20

 

 

전형적인 BFS문제로, 아이디어 하나만 떠올리면 쉽게 풀 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

일반적인 BFS문제 같은 경우는, 시작점이 하나만 주어져서 그냥 하면 되는데, 이 문제 같은 경우, 불도 상근이처럼 네 방향으로 퍼진다고 했으므로, 불도 시작점에 넣고 BFS를 돌려주어야 한다.

 

이때, 불과 상근이는 당연히 따로따로 처리해줘야한다.

 

불과 상근이를 시작점으로 맨 처음에 넣을 때 유의해야 할 점은, 상근이는 이제 곧 불이 붙으려는 칸으로 이동 할 수 없다는 사실이다.

 

이 사실 때문에, 시작점을 큐에 넣을 때, 상근이를 맨 뒤에, 불을 맨 앞에 넣어야 한다는 점이 다르다.

 

 

방문처리는 그래프를 직접 변형시킴으로써 했는데, 나는 상근이가 지금까지 지나간 칸과 불이 번지는 칸을 따로 구분하여 색칠하였다.

 

이때, 이미 불이 붙은 칸은 상근이가 못 지나가도록 방문처리를 해주었고, 불이 붙을 때에는 상근이가 이미 방문 처리한 칸을 제외한 빈칸을 방문처리해주었다.

 

물론, 상근이가 이미 지나갔던 칸에 다시 불이 붙을 수도 있지 않냐고 할 수 있을 수도 있지만, 한번 돌릴 때마다 어차피 한 칸밖에 번지지 않고, 이미 상근이가 지나갔던 칸에 불이 붙어봤자 도착지점으로 가는 상근이를 불이 따라잡을 수 없기 때문이다.

 

이후, 상근이가 그래프의 테두리로 가면 종료하고 최단 시간을 출력하도록 했다.

 

그렇지 않은 경우 impossible을 출력하도록 해주었다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 5427번 불
# 그래프 이론, 그래프 탐색, BFS
'''
접근 방법:
상근이, 불, 전부다 넣고 BFS돌리자.
가장자리 칸에 도달하면 도착한 것으로 간주하자.
'''
import sys
from collections import deque
input = sys.stdin.readline
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
def BFS(M, N, graph):
    start_R, start_C = 0, 0
    queue = deque()
    for i in range(N):
        for j in range(M):
            if graph[i][j] == '@':
                start_R, start_C = i, j
                queue.append((start_R, start_C, 0))
            elif graph[i][j] == '*':
                queue.appendleft((i, j, 0))
    while queue:
        row, col, time = queue.popleft()
        if (row == 0 or row == N-1 or col == 0 or col == M-1) and graph[row][col] == '@':
            return time+1
        if graph[row][col] == '*':
            for i in range(4):
                now_row, now_col = row+dr[i], col+dc[i]
                if now_row < 0 or now_row >= N or now_col < 0 or now_col >= M:
                    continue
                if graph[now_row][now_col] == '#':
                    continue
                if graph[now_row][now_col] == '.':
                    graph[now_row][now_col] = '*'
                    queue.append((now_row, now_col, time+1))
        else:
            for i in range(4):
                now_row, now_col = row+dr[i], col+dc[i]
                if now_row < 0 or now_row >= N or now_col < 0 or now_col >= M:
                    continue
                if graph[now_row][now_col] == '#' or graph[now_row][now_col] == '*':
                    continue
                if graph[now_row][now_col] == '.':
                    graph[now_row][now_col] = '@'
                    queue.append((now_row, now_col, time+1))
    return "IMPOSSIBLE"

T = int(input())
for _ in range(T):
    M, N = map(int, input().rstrip().split())
    graph = [list(input().rstrip()) for _ in range(N)]
    print(BFS(M, N, graph))