[Python] 4179번 불!

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

4179번: 불!

---

 

22/11/24

 

 

2022.11.29 - [백준 문제 풀이] - [Python] 5427번 불

[Python] 5427번 불

이 문제와 거의 같은 문제이지만, 테스트 케이스가 하나만 주어진다는 점, 그리고 M과 N이 아니라 R과 C로 주어져서 그래프의 입력을 다르게 받아야 된다는 점만 다르다.

---

 

문제 접근 방식:

 

 

맨 처음에 이 문제를 접했을 때는 5427번 불 문제와 거의 같은 모양이라 그냥 코드만 복붙하고 살짝 고친 후에 제출하려 했으나, 중간에 몇 번 실패했었다.

 

실패했던 큰 이유는 행과 열이 다르게 받아진다는 점이였다.

 

이 점을 간과하고 다른 부분이 틀린 줄 알고 삽질했었다.

 

그래서 5427번 문제와 비교했을 때 코드가 살짝 다른데, 이 코드는 시작점을 큐에 넣을 때 불을 뒤에 넣고 지훈이를 앞에 넣었다.

 

이후 불이 BFS를 진행할 때 지훈이가 지났던 칸도 지나가게끔 고쳐주었다.

 

사실 이렇게 구현해도 맞는 이유는 이번에는 불이 먼저가 아니라 지훈이가 먼저이기 때문에 가능한 것이다.

---

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

# 4179번 불!
# 그래프 이론, 그래프 탐색, 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] == 'J':
                start_R, start_C = i, j
                queue.appendleft((start_R, start_C, 0))
            elif graph[i][j] == 'F':
                queue.append((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] == 'J':
            return time+1
        if graph[row][col] == 'F':
            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] == '.' or graph[now_row][now_col] == 'J':
                    graph[now_row][now_col] = 'F'
                    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] == 'F':
                    continue
                if graph[now_row][now_col] == '.':
                    graph[now_row][now_col] = 'J'
                    queue.append((now_row, now_col, time+1))
    return "IMPOSSIBLE"

R, C = map(int, input().rstrip().split())
graph = [list(input().rstrip()) for _ in range(R)]
print(BFS(C, R, graph))