[백준] 4179번 불! - 파이썬(Python)

문제 (링크)

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

4179번: 불!

 

나의 풀이

# 오답
import sys
from collections import deque

input = sys.stdin.readline

move = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1]
]

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

dist = [[int(1e9)] * c for _ in range(r)]

q_jihun = deque()
q_fire = deque()
graph = []

for i in range(r):
    tmp = list(input().rstrip())
    for j in range(len(tmp)):
        if tmp[j] == 'J':
            q_jihun.append((i, j))
            dist[i][j] = 1
        
        elif tmp[j] == 'F':
            q_fire.append((i, j))
    
    graph.append(tmp)

# 지훈이 움직이는 BFS
def bfs_jihun(graph):
    x, y = q_jihun.popleft()
    if graph[x][y] == "F":
        dist[x][y] = 0
        return

    for i in range(4):
        nx = x + move[i][0]
        ny = y + move[i][1]

        if 0 <= nx < r and 0 <= ny < c:
            if graph[nx][ny] == ".":
                graph[nx][ny] = 'J'
                dist[nx][ny] = dist[x][y] + 1
                q_jihun.append((nx, ny))

# 불이 퍼지는 BFS
def bfs_fire(graph, x, y):
    for i in range(4):
        nx = x + move[i][0]
        ny = y + move[i][1]

        if 0 <= nx < r and 0 <= ny < c:
            if graph[nx][ny] != "#" and graph[nx][ny] != "F":
                q_fire.append((nx, ny))
                graph[nx][ny] = "F"


current = deque()
while q_jihun:
    # 1분마다
    bfs_jihun(graph)

    for _ in range(len(q_fire)):
        x, y = q_fire.popleft()
        current.append((x, y))

    while current:
        a, b = current.popleft()
        bfs_fire(graph, a, b)
    
min_value = int(1e9)

for i in range(c):
    min_value = min(dist[0][i], min_value) # 맨 윗 줄
    min_value = min(dist[r-1][i], min_value) # 맨 아래 줄

for j in range(r):
    min_value = min(dist[j][0], min_value) # 왼쪽 줄
    min_value = min(dist[j][c-1], min_value) # 오른쪽 줄


if min_value == int(1e9):
    print("IMPOSSIBLE")

else:
    print(min_value)

최근 푼 문제들 중 가장 삽질을 했지만 나름 의미 있는 삽질인 것 같다.

 

처음에 문제에 접근할 때는 1분마다 불이 퍼지는 것과 지훈이 움직이는 것을 업데이트 해주고 싶었다.

 

지훈은 1분에 한 칸밖에 못가지만, 불은 1분에 인접한 네 방향에 모두 퍼진다.

 

따라서, 한 타임에 q_fire에 들어있는 값들을 모두 pop한 후 해당 값들에 대한 bfs를 모두 돌아주고, 지훈은 q_jihun에 들은 값은 하나만 pop해 움직이게 함으로써, 결과적으론 내가 원하는대로 움직이게 할 수 있었다.

 

실제로 while q_jihun: 코드 블럭에 있는 동작을 한 회 수행하고 난 후 graph를 프린트 해보면 다음과 같은 결과가 나온다.

 

이렇듯 잘 움직여준 후, 지훈이 움직인 거리를 기록하기 위한 dist 리스트를 만들어 매번 1씩 더해주었다.

 

마지막 부분이 굉장히 골 때렸는데, 결국 지훈이 탈출하기 위해선 그래프의 가장자리까지 dist 값이 찍혀야한다.

 

즉, 사각형의 변 부분 중 가장 최소값을 찾아줘야하는 것이다. 이 부분은 반복문으로 처리해줬다.

 

테스트 케이스에 대해선 올바른 답이 나왔으나, 실제 채점시에는 오답이 떴다. 

하..

 

결국 다른 사람들의 코드를 통해 힌트를 좀 얻었고, 내 접근법이 너무 무식했음을 깨달았다.

 

import sys
from collections import deque

input = sys.stdin.readline
r, c = map(int, input().split())
graph = []

q_j = deque()
q_f = deque()

visited_j = [[0] * c for _ in range(r)]
visited_f = [[0] * c for _ in range(r)]

move = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1]
]

for i in range(r):
    temp = list(input())

    for j in range(len(temp)):
        if temp[j] == "J":
            q_j.append((i, j))
            visited_j[i][j] = 1
        
        elif temp[j] == "F":
            q_f.append((i, j))
            visited_f[i][j] = 1
        
    graph.append(temp)

def bfs():
    while q_f:
        x, y = q_f.popleft()

        for i in range(4):
            nx, ny = x + move[i][0], y + move[i][1]

            if 0 <= nx < r and 0 <= ny < c:
                if not visited_f[nx][ny] and graph[nx][ny] != "#":
                    visited_f[nx][ny] = visited_f[x][y] + 1
                    q_f.append((nx, ny))

    while q_j:
        x, y = q_j.popleft()

        for i in range(4):
            nx, ny = x + move[i][0], y + move[i][1]

            if 0 <= nx < r and 0 <= ny < c:
                if graph[nx][ny] != "#" and not visited_j[nx][ny]:
                    if not visited_f[nx][ny] or visited_f[nx][ny] > visited_j[x][y] + 1:
                        visited_j[nx][ny] = visited_j[x][y] + 1
                        q_j.append((nx, ny))

            else:
                return visited_j[x][y]

    
    return "IMPOSSIBLE"

print(bfs())

애초에 불이 퍼지는 것을 기록할 visited_f와 지훈의 이동을 기록할 visited_j를 따로 만들어 각각을 BFS로 돌아주고 이동거리를 기록해준다.

 

특히, 지훈의 이동거리를 기록하는 부분이 중요한데, 불이 이미 퍼지지 않은 곳이거나 혹은 불이 도달하는 시간보다 더 짧은 시간안에 지훈이 도달할 수 있다면 해당 위치에 대한 값을 기록해주면 된다.

 

그러다가 만약 nx와 ny가 범위를 벗어나게 된다면 지훈이 무사히 탈출한 것으로 간주할 수 있으므로 x와 y까지의 이동거리를 리턴해주면 답을 구할 수 있다.