글 읽기 - 5427 불 bfs로 풀었는데 시간초과가 나네요...ㅠㅠ

jadebaek 5년 전 0

대략적인 구조는

while(큐가 비지 않음) {

if(큐가 불일 경우) {

불이 사방으로 퍼짐

방금 퍼진 불 위치 큐에 저장

continue

}

상근이 이동

방금 기록된 상근이 위치 큐에 저장

}

while이 끝나도 함수가 끝나지 않은 경우 - IMPOSSIBLE

입니다.

count는 단계별로 상근이가 이동하는 경로이고,

45~46번째 줄은 상근이가 방금 있던 자리에 불이 오는 경우에 대비해서 예외처리 해놓은 겁니다.

토마토 문제도 중간까지 가고나서 시간초과 뜨던데... 제 bfs 구성에 문제가 있는 것 같습니다.

고수분들의 도움을 요청해요!! ㅠㅠ

import sys


def bfs():
    global count, h, status
    while(len(queue) != 0):

        tempr = queue[0][0] # 큐에 있던 좌표
        tempc = queue[0][1]
        del queue[0]
        tempfirer = -1
        tempfirec = -1

        if building[tempr][tempc] == '*': # 불
            for i in range(4):
                if 0<=tempr+direction[i][0]<h and 0<=tempc+direction[i][1]<w:
                    if building[tempr+direction[i][0]][tempc+direction[i][1]]=='.': # 범위 내이며 .일 때 옮겨붙는다.
                        building[tempr+direction[i][0]][tempc+direction[i][1]] = '*'
                        queue.append([tempr+direction[i][0], tempc+direction[i][1]]) # 새로 불이 붙은 자리를 다시 큐에 저장한다.
                    elif building[tempr+direction[i][0]][tempc+direction[i][1]] == count-1:  # 방금 전까지 사람이 있던 자리
                        tempfirer = tempr+direction[i][0]
                        tempfirec = tempc+direction[i][1]
                        queue.append([tempfirer, tempfirec])
            if status == 1:
                count += 1
                status = 0
            continue

        # 상근이의 이동
        status = 1
        for i in range(4):
            # 가려는 자리에 아무것도 없는 경우. 즉 갈 수 있는 경우
            if building[tempr+direction[i][0]][tempc+direction[i][1]] == '.':
                if tempr+direction[i][0]==0 or tempr+direction[i][0]==h-1 or tempc+direction[i][1]==0 or tempc+direction[i][1]==w-1: # 도착
                    print(building[tempr][tempc]+1)
                    return
                building[tempr+direction[i][0]][tempc+direction[i][1]] = count
                queue.append([tempr+direction[i][0], tempc+direction[i][1]])
            # 벽도 아니고 불도 아님. 즉 기존에 갔던 숫자
            elif building[tempr+direction[i][0]][tempc+direction[i][1]] != '#' and building[tempr+direction[i][0]][tempc+direction[i][1]] != '*':
                if count < building[tempr+direction[i][0]][tempc+direction[i][1]]:
                    building[tempr+direction[i][0]][tempc+direction[i][1]] = count
                    queue.append([tempr+direction[i][0], tempc+direction[i][1]])

        if tempfirer!=-1 and tempfirec!=-1:
            building[tempfirer][tempfirec] = '*' # 아까 보류했던 불

    print("IMPOSSIBLE")
    return


direction = [[0,1], [0,-1], [1,0], [-1,0]]
n = int(sys.stdin.readline().rstrip()) # 테케 개수
for tc in range(n):

    w, h = map(int, sys.stdin.readline().rstrip().split())
    building = [0 for i in range(h)]
    for i in range(h):
        building[i] = list(input()) # 여기까지 입력받는다
    count = 1
    queue = []
    status = 1 # 0:fire, 1:human

    startx = -1
    starty = -1
    for i in range(h):
        for j in range(w):
            if building[i][j] == '@':
                startx = i
                starty = j
                building[i][j] = 1
            elif building[i][j] == '*':
                queue.append([i, j])
    queue.append([startx, starty])

    bfs()

hello70825 5년 전 1

del queue[0]은 queue.pop(0)과 똑같이 시간 복잡도가 O(N)입니다.

그래서 O(1)로 뺄 수 있는 deque를 사용하셔야 합니다

그리고 상근이가 이동할 때 범위 확인해주셔야 합니다.

반례 드립니다.

둘 다 답은 1인데 하나는 에러가 나오고, 하나는 답이 다르게 나옵니다.

1
2 2
..
.@

1
2 2
@.
.*

jadebaek 5년 전 1

답변 감사드립니다!! del의 시간복잡도를 몰랐네요 ㅠㅠ

많은 도움이 되었습니다 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

5427 불 bfs로 풀었는데 시간초과가 나네요...ㅠㅠ

jadebaek 5년 전 0

hello70825 5년 전 1

jadebaek 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말