[BOJ] 4179. 불! (Python) / BFS

www.acmicpc.net/problem/4179

4179번: 불!

전형적인 최단거리 구하기 BFS 문제이다.

 

처음 아이디어는 사람이 먼저 4방향으로 뛰고, 불을 퍼트리고, 사람 이동, 불 이동 이런 식으로 번갈아 해줬는데 어디서 꼬였는지 자꾸 70%대에서 계속 틀렸다. 

3번 넘게 계속 틀렸습니다가 떠서 질문검색을 통해

1. 불을 먼저 완전히 퍼트리고 이 정보를 보고 2. 사람이 격자 밖으로 나갈 수 있는지 여부를 확인함을 알았다. 

• 불이 각 위치에 도달한 정보를 fire 맵에 저장하고(fbfs 함수), 
• 이를 기반으로 사람이 bfs로 최단거리 이동을 하는데(hbfs 함수),
  • 이 때 불이 이미 퍼진 곳이고, 자신이 이동해온 거리가 불이 도달한 거리보다 작다면 이동할 수 없다.
  • 이동할 수 있는 위치에는 그 동안의 거리에 +1을 해주어 human 맵에 정보를 저장한다.
  • 이동할 수 있는 위치는 계속 큐에 담아주며 나아간다.
• 격자 밖으로 나가는 순간, 탈출 => 현 위치 정보 출력하고 종료.

 

파이썬 코드는 다음과 같다.

---

import sys
input = sys.stdin.readline
from collections import deque

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def fbfs():
    while fq:
        r, c = fq.popleft()
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < R and 0 <= nc < C):
                continue
            if maze[nr][nc] == "#" or fire[nr][nc]:
                continue
            fire[nr][nc] = fire[r][c] + 1
            fq.append((nr, nc))

def hbfs():
    while hq:
        r, c = hq.popleft()
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < R and 0 <= nc < C):
                print(human[r][c])
                return
            if human[nr][nc] or maze[nr][nc] == "#":
                continue
            if fire[nr][nc] and human[r][c] + 1 >= fire[nr][nc]:
                continue
            human[nr][nc] = human[r][c] + 1
            hq.append((nr, nc))
    print("IMPOSSIBLE")
    return

# main
R, C = map(int, input().split())
maze = []
hq = deque()
fq = deque()
human = [[0] * C for _ in range(R)]
fire = [[0] * C for _ in range(R)]
for i in range(R):
    maze.append(list(input().strip()))
    for j in range(C):
        if maze[i][j] == "J":
            hq.append((i, j))
            human[i][j] = 1
        elif maze[i][j] == "F":
            fq.append((i, j))
            fire[i][j] = 1
fbfs()
hbfs()

---

• 실행시간 508ms / 메모리 192056kb
• 고찰 : 쉽게 생각하다가 오히려 도중에 로직을 바꾸며 시간이 오래 걸린 문제이다. (1시간 40분 소요) 재미있는 최단거리 문제였다. 비슷한 유형의 문제가 나오면 어렵지 않게 풀 수 있을 것 같다. 항상 자신감을 갖자!