글 읽기 - python bfs 시간초과입니다 고수님들 살려주세요

lhs0831 1년 전 0

안녕하세요

BFS로 풀었는데 자꾸 시간초과가 뜨네요ㅠ

방문하기 전에 방문할 노드를 큐에 넣는 거도 했고

방문한 노드 체크도 flag리스트로 처리를 해서 O(1)인 것 같은데

왜 자꾸 시간 초과가 뜨는지 답답합니다. 아마 제 잘못이겠지만..

고수님의 명쾌한 해답 부탁드립니다.

import sys
from collections import deque
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
print = sys.stdout.write
############################입력 처리
n, m = map(int, input().split())
arr = [[] for _ in range(n+1)]
ans = [0 for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    arr[b].append(a)

###############bfs 함수 
def bfs(start):
    flag = [0] * (n+1)
    q = deque([start])
    flag[start] = 1
    while q:
        node = q.popleft()
        ans[start] += 1
        for i in arr[node]:
            if flag[i] == 0:
                flag[i] = 1
                q.append(i)
#########################메인                
maxlist = list()
mx = -1
for i in range(1, n+1):
    if len(arr[i]) != 0:
        bfs(i)

    if ans[i] > mx:
        maxlist.clear()
        mx = ans[i]
        maxlist.append(i)
    elif ans[i] == mx:
        maxlist.append(i)
    else:
        continue

#######################정답 출력
for i in maxlist: 
    print(str(i) + " ")

adung7 1년 전 0

pypy3로 제출해보세요

adung7 1년 전 0

아 3번째 줄 지워야합니다

aru0504 1년 전 0

BFS는 방문체크를 방문 전에 해야 합니다.

q.append를 하는 때에 함께 처리해주세요!

adung7 1년 전 0

flag리스트가 방문체크 하는거라 그거는 상관없을거 같아요 3번째 줄만 지우고 pypy3로 제출했더니 AC받았습니다

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

문제

문제

출처

ICPC

python bfs 시간초과입니다 고수님들 살려주세요

lhs0831 1년 전 0

adung7 1년 전 0

adung7 1년 전 0

aru0504 1년 전 0

adung7 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말