글 읽기 - BFS 메모리초과 - 어떤 부분을 고쳐야 할지 도와주세요..

mhl123 1년 전 0

BFS 로 풀었는데 계속 메모리 초과가 납니다..

어느 부분을 고쳐야 할지 도와주세요...!! ㅜㅜ

#연결요소의 개수
from collections import deque
import sys
input = sys.stdin.readline

n,m = map(int,input().split())
graph=[[] for _ in range(n+1)]
for _ in range(m):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

visited=[False for i in range(n+1)]

def bfs(graph, v):
    q = deque([v])
    while q:
        cur = q.popleft()
        visited[cur] = True
        length = len(graph[cur])
        for i in range(length):
            elem = graph[cur][i]
            if not visited[elem]:
                q.append(elem)

cnt = 0
for i in range(1, n+1):
    if not visited[i]:
        bfs(graph, i)
        cnt += 1
print(cnt)

ohwonteak 1년 전 2

19번째 줄 visited[cur]= True가 19번째 있는것과 24번째 줄에 넣어주는거랑 어떨지 한번 머릿속에서 그려보세요
즉 방문체크를 큐에서 뺄때와 큐에다가 넣을때 큐에 들어가는 데이터의 중복량을 한번 생각해보시면 아실겁니다

mhl123 1년 전 0

와 감사합니다!!

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

문제

문제

출처

ICPC

BFS 메모리초과 - 어떤 부분을 고쳐야 할지 도와주세요..

mhl123 1년 전 0

ohwonteak 1년 전 2

mhl123 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말