글 읽기 - 이 두코드의 차이점을 잘 모르겠어요 (bfs 방문처리)

zezering2192 1년 전 0

처음 코드는 while문 안에서 queue.popleft()를 해서 뽑혀진 값을 방문처리 해줬는데 시간초과가 떴고,

두번째 코드는 첫 시작 노드를 queue에 넣고 방문처리 + 연결된 노드를 queue에 append하고 난 후에 방문처리 해줬더니 테스트를 통과했습니다.

queue에 값을 append하고 다시 popleft()로 뽑아낸 후에 방문처리하는거랑 뭐가 다른건지 모르겠어요ㅜㅜ 똑같아 보이는데 시간초과가 나는 이유를 알고싶습니다

from collections import deque
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
count = 0

for _ in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

def bfs(v):
    queue = deque([v])

    while queue:
        v = queue.popleft()
        visited[v] = True

        for e in adj[v]:
            if not visited[e]:
                queue.append(e)

for i in range(1, n + 1):
    if not visited[i]:
        bfs(i)
        count += 1

print(count)

--------------------------------------

from collections import deque
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
count = 0

for _ in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

def bfs(v):
    queue = deque([v])
    visited[v] = True

    while queue:
        v = queue.popleft()

        for e in adj[v]:
            if not visited[e]:
                queue.append(e)
                visited[e] = True

for i in range(1, n + 1):
    if not visited[i]:
        bfs(i)
        count += 1

print(count)

0000000000 1년 전 3

방문처리를 큐에서 뺄 때 하면 큐에 중복 정점이 들어갈 수 있습니다. 이렇게 되면 큐에 너무 많은 정점이 들어가 메모리 초과가 나거나 같은 정점을 여러 번 방문하는 바람에 시간 초과가 날 수 있습니다.

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

문제

문제

출처

ICPC

이 두코드의 차이점을 잘 모르겠어요 (bfs 방문처리)

zezering2192 1년 전 0

0000000000 1년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말