글 읽기 - python3] BFS vs DFS 질문

mimmyum 6년 전 0

위 문제를 BFS로 푸니깐 시간초과가 나오고 DFS로 푸니깐 정상적으로 정답판정을 받았는데요

어떤 점에서 BFS가 시간초과를 받는걸까요... 코드가 이상하게 짠건지...

visited 배열에서 이미 한번 통과한 정점은 제외하고 추가하게 해놓아서 그렇게 많이 반복문을 안돌꺼라고 생각했는데...

#DFS로 푼 경우의 코드의 일부

def dfs(visited,vertex) :
    if visited[vertex] == 1 :
        return
    visited[vertex] = 1
    for i in graph[vertex] :
        if visited[i] != 1 :
            dfs(visited,i)
'''
(중략)
'''
    visited = [0]*(N+1)
    total = 0

    for i in range(1,N+1) :
        if visited[i] ==1 :
            continue
        dfs(visited,i)
        total+= 1

#BFS로 푼 경우의 코드(일부)
   
    total = 0
    for i in range(1,N+1) :
        queue = []
        if visited[i] == 1 :
            continue
        queue.append(i)

        while queue :
            now = queue.pop(0)
            if visited[now] == 1 :
                continue
            visited[now] = 1
            for j in graph[now] :
                if visited[j] == 0 :
                    queue.append(j)

        total += 1

djm03178 6년 전 0

BFS는 큐에서 뺀 다음이 아니라, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다.

jh05013 6년 전 1

queue.pop(0)은 첫 번째 원소를 빼고 나머지 원소를 하나하나 왼쪽으로 옮깁니다. 절대로, 절대로, 절대로, 절대로 하면 안 됩니다.

mimmyum 6년 전 0

위에 두분들 답변 감사드립니다 ㅠㅠ

@djm03178
BFS를 한번 더 공부해보고
집에가서 다시한번 코드를 짜봐야겟네요

@jh05013
pop에서 시간이 잡아 먹힐 수도 있겠군요... 예전에도 비슷한 질문한 적이 있는데
그때는 덱을 쓰면 O(1)이라 괜찮을 수도 있다고 햇는데 한번 덱으로도 해봐야겠습니다.

두분다 답변 정말 감사드립니다.

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

문제

문제

출처

ICPC

python3] BFS vs DFS 질문

mimmyum 6년 전 0

djm03178 6년 전 0

jh05013 6년 전 1

mimmyum 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말