[정글 week04] 백준 코테 불!

벌써 4주차 시험
3주차 시험을 보고 다 틀려......복습하면서
비슷한 문제 풀어보기!

문제

시험에서 풀었던 경쟁적 전염과 비슷한 문제라 했으니
비슷하게 접근
문제 자체도 전염이 퍼지는 것과, 불이 퍼지는 것 비슷하다.

입출력

그렇다.

불이 퍼지는 시간을 확인
지훈이가 이 시간보다 빨리 '.'을 뛰어간다면 탈출 가능
뛰어라

문제 속 난관

경쟁적 전염과 비슷하기에, 경쟁적 전염처럼 풀었다.

R*C 순회하면서 '#'이 아닌 곳에 대한 정보를 가져와서,
지훈이가 이동하고, 불이 이동하는 것으로 판단.

하지만?
메모리 초과

도대체 왤까?
도저히 생각이 안나서 AI에게 도움을 받았다.

1. 불이 퍼짐는 BFS 실행
2. 지훈이가 이동하는 BFS 실행

이렇게 분리하라고 한다.

from collections import deque

R, C = list(map(int, input().split()))
maps = [list(input().strip()) for _ in range(R)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# ================ 불 ================
fire_q = deque()
fire_time = [[-1] * C for _ in range(R)]

for i in range(R):
    for j in range(C):
        if maps[i][j] == "F":
            fire_q.append((i, j))
            # 초기 시간 값
            fire_time[i][j] = 0

while fire_q:
    x, y = fire_q.popleft()
    
    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y

        if 0 <= nx < R and 0 <= ny < C and maps[nx][ny] == ".":
            if fire_time[nx][ny] == -1:
                # 다음시간 = 현재 시간 + 1
                fire_time[nx][ny] = fire_time[x][y] + 1
                fire_q.append((nx, ny))
# ================ 불 ================

# ================ 지훈 ===============
ji_q = deque()
ji_time = [[-1] * C for _ in range(R)]
for i in range(R):
    for j in range(C):
        if maps[i][j] == "J":
            ji_q.append((i, j))
            # 초기 시간 값
            ji_time[i][j] = 0

flag = False
result = 0
while ji_q:
    x, y = ji_q.popleft()
    
    # 가장 자리에 도달했다면 탈출 가능
    if x == 0 or x == R-1 or y == 0 or y == C-1:
        result = ji_time[x][y] + 1
        flag = True
        break

    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y

        if 0 <= nx < R and 0 <= ny < C:
            if ji_time[nx][ny] == -1 and maps[nx][ny] == ".":
                # 현재 불이 방문을 안한 곳이거나, 현재 시간 + 1 보다 적어야 탈출 가능
                if fire_time[nx][ny] == -1 or ji_time[x][y] + 1 < fire_time[nx][ny]:
                    ji_time[nx][ny] = ji_time[x][y] + 1
                    ji_q.append((nx, ny))

print(result) if flag else print("IMPOSSIBLE")

반복과 조건이 꽤 많이 들어갔다고 생각하지만 더 좋은 방법이 생각나지 않기에...

지훈이의 조건은 그렇다.
1. 다음 x, y가 0 보다 크고 R, C 보다 작아야 한다.
2. 다음 x, y는 방문하지 않은 곳이여야 하고 맵은 이동 가능한 '.' 이여야 한다.
3. 불의 다음 x, y가 -1 이거나 불이 퍼지는 시간보다 현재 이동 시간 + 1이 더 빨라야 한다.

nx, ny가 next의 약자였단걸 어제 처음 알았다.
물론 어제 처음 봤다.

알고나니 더 이해가 잘 가는군.

시간 복잡도

불 BFS : O(RC)
지훈이 BFS : O(RC)
=> O(RC + RC) = O(R*C)

공간 복잡도

maps : O(RC)
fire_time : O(RC)
ji_time : O(RC)
fire_q, ji_q : 최악의 경우 O(RC)
=> O(R*C)

BFS와 DFS를 이해했다고 생각했지만 막상 시험에서 적용을 잘 못했다...
이해할 때까지 문제를 풀어보어야 할 듯 하다.