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

문제

풀이

진짜 이 문제 뭘까
어제부터 날 고생시키는 불...이야...

솔직히 문제 자체는 별로 어렵지 않았다
불! 이랑 똑같다
그래서 코드를 똑같이 냇다

따란!

불!이랑 전혀 다른 게 없는데 자꾸 12%에서 터졌다
질문 게시판을 다 뒤져봐도 내가 놓친 조건이나 고려사항이 전혀 없는데다가 심지어 테케랑 반례까지 다 넣어도 틀린 걸 찾을 수가 없어서 답답해 미칠 지경이엇는데

자 틀린 그림 찾기 시작~!

은 개뿔 그냥 코드를 옮기는 과정에서 time += 1 부분이 지워져버려서 제대로 된 time이 출력되지 않아 나는 에러였다

최종 코드

# 1792ms

def find_JF():
    global J, F
    for i in range(h):
        for j in range(w):
            if MAZE[i][j] == '*':
                F.append((i, j))
            elif MAZE[i][j] == '@':
                J = [i, j]

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

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

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

        jq = jq[_l:]
        time += 1

    return 'IMPOSSIBLE'

for _ in range(int(input())):
    w, h = map(int, input().split())
    MAZE = [list(input()) for _ in range(h)]
    J, F = [], []

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

후기

저거 찾으려고 이 문제가 출제된 대회 사이트까지 들어가서 수백줄의 반례까지 다운받아서 입력해봤다
이거 때매 30분 날림 ^^