[BOJ] 4179. 불! (🥇, BFS/DFS)

문제

풀이

오랜만에 풀어본 BFS 문제였는데 이 문제는 진짜 실수를 겁나 많이 했다...

우선 로직 자체는,

1. 불이 먼저 확산한다
2. 지훈이가 이동한다
3. 지훈이가 이동할 수 있는 칸에 범위를 벗어나는 칸이 있다면 시간 출력 후 종료
4. 지훈이가 더 이상 이동할 수 있는 칸이 없다면 탈출 불가 IMPOSSIBLE 출력

불은 #이 아닌 모든 곳을 방문 가능하고, 불이 지나간 곳은 # 처리
지훈이는 .인 곳만 방문 가능하고, 지훈이가 지나간 곳은 J

1. 지훈이와 불은 동시에 확산되지만 불은 지훈이가 이동한 곳으로 갈 수 있어도 지훈이는 불이 있는 곳으로 갈 수 없기 때문에 불이 먼저 이동
2. 지훈이가 이후에 불이 없는 칸만 이동
3. 탈출구는 가장자리에 있다고 했으므로 가장자리에 닿는다면 그때 시간이 탈출 시간
4. 불이 이동한 후에 지훈이가 이동했는데 더 이상 이동할 칸이 없다면 탈출이 불가한 것이므로 IMPOSSIBLE.

실수1

지훈이가 이동할 수 있는 칸이 여러 칸일 때를 고려하지 않음

1초 그래프
F F . . F F F
F # # . # # .
. # # J # # .
. . J J J . .
. # # J # # .
F # # . # # .
F F . . F F F
2초 그래프
F F F F F F F
F # # . # # F
F # # J # # .
. . J J J . .
F # # J # # .
F # # J # # F
F F F F F F F
3초 그래프
F F F F F F F
F # # F # # F
F # # J # # F
F . J J J . .
F # # J # # F
F # # F # # F
F F F F F F F
4초 그래프
F F F F F F F
F # # F # # F
F # # F # # F
F F J J J J F
F # # F # # F
F # # F # # F
F F F F F F F

정가운데 J가 실제 지훈이의 출발점
거기서 4방향으로 뻗어나가게 되는데, 이때 4방향 모두가 확산 -> 불이 확산 -> 4방향에서 확산된 칸들에서 또 확산 ->... 이렇게 진행되어야 한다.
그런데 지금은 4방향 중 1방향만 확산 -> 불 확산 -> 나머지 중 또 1방향 확산 -> 불 확산.. 이런 식이라서 불의 번짐속도가 훨씬 빨라 무조건 탈출이 불가한 상태가 됨

def exodus(J, fq):
    jr, jc = J
    MAZE[jr][jc] == 'J' # 지훈이가 방문했던 곳을 또 방문하지 않도록 하기 위해서
    jq = [(jr, jc)]
    time = 1
    # 지훈이가 이동할 수 있는 지역이 있나?
    while jq:

        # 불이 먼저 확산되고
        new_fq = []
        for fr, fc in fq:
            for nr, nc in (fr-1, fc), (fr+1, fc), (fr, fc-1), (fr, fc+1):
                if nr<0 or nc<0 or nr>=R or nc>=C or MAZE[nr][nc] == '#':
                    continue
                new_fq.append((nr, nc))
                MAZE[nr][nc] = '#'

        fq = new_fq[:]

        # 불과 벽, 이미 지훈이가 방문한 공간을 제외하고 지훈이가 이동할 수 있는 방향으로 확산
        # 더 갈 수 있는 곳이 없다면 ....
        jr, jc = jq.pop(0)
        for _nr, _nc in (jr+1, jc), (jr-1, jc), (jr, jc+1), (jr, jc-1):
            if _nr<0 or _nc<0 or _nr>=R or _nc>=C:
                return time
            
            if MAZE[_nr][_nc] != '.':
                continue
            
            MAZE[_nr][_nc] = 'J'
            jq.append((_nr, _nc))

        time += 1

    return 'IMPOSSIBLE'

불의 경우 for문으로 모든 불이 확산하는데 지훈이는 jr, jc 딱 하나의 칸만 이동하는 것이었다... 지훈이의 이동 방식도 pop을 사용하는게 아니라 for문으로 바꿔주었다

new_jq = []
for jr, jc in jq:
    for _nr, _nc in (jr+1, jc), (jr-1, jc), (jr, jc+1), (jr, jc-1):
        if _nr<0 or _nc<0 or _nr>=R or _nc>=C:
            return time
        
        if MAZE[_nr][_nc] != '.':
            continue
        
        MAZE[_nr][_nc] = 'J'
        new_jq.append((_nr, _nc))

jq = new_jq[:]

실수2 (메모리 초과)

이 실수는 진짜 멍청했다... 위의 실수1을 고치려고 디버깅하려다가 터진 에러였기 때문이다.

일단 불이 방문한 곳은 # 처리를 해서 재방문하지 않게 하고 있었는데, 디버깅한답시고 이걸 F로 바꿔뒀던 걸 고치지 않아서 터진 에러였다...

• F로 했을 때
  

• #로 했을 때
  

한 마디로 걍 방문처리 안 해줘서 터진 문제 ㅎㅎ

그외 실수...

그 외에도 jq 리스트 new_jq로 안 바꿔서 터진 문제
new_jq랑 new_fq 쓴 것 때문에 메모리 초과 터진 줄 알고 코드 수정한 멍청이 같은 문제ㅜ
l이랑 _l 헷갈린 문제 등 성격 급해서 그냥 제출했다가 사소한데서 오타난 자잘한 실수들이 있었다..

최종코드

# 908ms

def find_JF():
    global J, F
    for i in range(R):
        for j in range(C):
            if MAZE[i][j] == 'F':
                F.append((i, j))
            elif MAZE[i][j] == 'J':
                J = [i, j]

def exodus(J, fq):
    jr, jc = J
    MAZE[jr][jc] == 'J' # 지훈이가 방문했던 곳을 또 방문하지 않도록 하기 위해서
    jq = [(jr, jc)]
    time = 1
    # 지훈이가 이동할 수 있는 지역이 있나?
    while jq:

        # 불이 먼저 확산되고
        new_fq = []
        for fr, fc in fq:
            for nr, nc in (fr-1, fc), (fr+1, fc), (fr, fc-1), (fr, fc+1):
                if nr<0 or nc<0 or nr>=R or nc>=C or MAZE[nr][nc] == '#':
                    continue
                new_fq.append((nr, nc))
                MAZE[nr][nc] = '#'

        fq = new_fq[:]

        # 불과 벽, 이미 지훈이가 방문한 공간을 제외하고 지훈이가 이동할 수 있는 방향으로 확산
        # 더 갈 수 있는 곳이 없다면 ....
        new_jq = []
        for jr, jc in jq:
            for _nr, _nc in (jr+1, jc), (jr-1, jc), (jr, jc+1), (jr, jc-1):
                if _nr<0 or _nc<0 or _nr>=R or _nc>=C:
                    return time
            
                if MAZE[_nr][_nc] != '.':
                    continue
            
                MAZE[_nr][_nc] = 'J'
                new_jq.append((_nr, _nc))
                
        jq = new_jq[:]
        time += 1

    return 'IMPOSSIBLE'

R, C = map(int, input().split())
MAZE = [list(input()) for _ in range(R)]
J, F = [], []

find_JF()
print(exodus(J, F))

후기

항상 BFS 만만하게 보고 푸는데 그래서인지 자잘한 실수를 겁나 많이 한다^^
근데 지난 상반기에 본 한 4번의 코테에서 bfs 문제 한 번도 안 나왔다 ㅎㅎ 다들 실력이 향상되긴 했는가보다ㅏ