백준 4179 불! - 골드4 [파이썬]

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

4179번: 불!

 

최단거리를 구하는 BFS와 시뮬레이션이 합쳐진 문제다.

불을 먼저 퍼트리고, 지훈이 그 다음 이동하도록 하였다.

그 반대로 하려면 좀 까다로웠기 때문이다.

 

불과 지훈이 한 번에 한 칸씩만 퍼져야 했기 때문에

queue에서 popleft 할 때 fcnt, jcnt 만큼만 꺼내서 퍼지도록 했다.

 

정답 소스코드

import sys
from collections import deque
input = sys.stdin.readline
R, C = map(int, input().split(" "))
graph = []
for i in range(R):
    s = input().rstrip()
    graph.append(list(s))

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

fqueue = deque()
jqueue = deque()

fcnt = 0
jcnt = 0
for r in range(R):
    for c in range(C):
        if graph[r][c] == 'F':
            fqueue.append((r, c))
            fcnt += 1
        if graph[r][c] == 'J':
            jqueue.append((r, c))
            jcnt += 1


time = 0
escaped = False
while True:
    time += 1
    # 불번짐 먼저 시작
    ftmp = 0
    for f in range(fcnt):
        r, c = fqueue.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < R and 0 <= nc < C:
                if graph[nr][nc] == 'J' or graph[nr][nc] == '.':
                    fqueue.append((nr, nc))
                    ftmp += 1
                    graph[nr][nc] = 'F'
    fcnt = ftmp

    # 지훈이 이동
    jtmp = 0
    died = True
    for j in range(jcnt):
        r, c = jqueue.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < R and 0 <= nc < C:
                if graph[nr][nc] == '.':
                    died = False
                    jqueue.append((nr, nc))
                    jtmp += 1
                    graph[nr][nc] = 'J'
            else:
                # 탈출 성공
                escaped = True
    jcnt = jtmp

    if escaped == True:
        print(time)
        break
    if died == True:
        print("IMPOSSIBLE")
        break

# 시뮬레이션과 BFS가 합쳐진 문제
# 반례를 찾느라 정말 많이 틀렸다..

결과

F가 하나도 없을 수 있다는 점을 간과해서 몇 번 틀렸고

jcnt를 사용하지 않고 단 1번만 popleft 해서 이상하게 퍼져서 몇 번 더 틀렸었다.

출력 초과는 디버깅용 print 삭제 안하고 제출했다가 틀린 것..

504ms -> 476ms 줄인 건 visited 배열을 쓰려고 선언만 해놓은거 안써도 풀리길래 삭제했더니 줄었다.