글 읽기 - 파이썬 bfs dfs 둘다 해봤는데 시간초과 뜨네요....

ppagse 1년 전 0

고수분들 도움 부탁드립니다..

#bfs

from collections import deque
import sys

n,m=map(int,input().split())
connect=[[]for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,sys.stdin.readline().split())
    connect[b].append(a)
ans=[0 for _ in range(n+1)]
for i in range(1,n+1):
    cnt=0
    queue=deque([i])
    visit=[0 for _ in range(n+1)]
    while queue:
        tmp=queue.popleft()
        cnt+=1
        visit[tmp]=1
        for j in connect[tmp]:
            if not visit[j]:
                queue.append(j)
    ans[i]=cnt
max=max(ans)
for i in range(1,n+1):
    if max==ans[i]:
        print(i,end=' ')
        
        
        
        
        
        
#dfs

import sys

sys.setrecursionlimit(10**9)

def dfs(i):
    global cnt
    cnt+=1
    visit.add(i)
    for j in connect[i]:
        if (j not in visit):
            dfs(j)
    return

n,m=map(int,input().split())
connect=[[]for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,sys.stdin.readline().split())
    connect[b].append(a)
ans=[0 for _ in range(n+1)]
for i in range(1,n+1):
    cnt=0
    visit=set()
    dfs(i)
    ans[i]=cnt
max=max(ans)
for i in range(1,n+1):
    if max==ans[i]:
        print(i,end=' ')

jstm1207 1년 전 0

PyPy3로 제출해보시면 어떨까요? 저도 Python3에서는 시간초과였는데 PyPy3에서는 통과했습니다. 그리고 지금 통과한 파이썬 코드들 몇 페이지 넘겨서 봤는데

모두 PyPy3 로 제출한 풀이였어요!

ppagse 1년 전 0

답변 감사합니다! bfs는 그대로 시간 초과가 뜨고 dfs는 메모리초과가 뜨네요...ㅠ

dfs코드에서 메모리 줄일 방법이 있을까요?

ppagse 1년 전 1

bfs코드 조금 수정하고 PyPy3으로 제출하니까 맞았습니다. 감사합니다!

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

문제

문제

출처

ICPC

파이썬 bfs dfs 둘다 해봤는데 시간초과 뜨네요....

ppagse 1년 전 0

jstm1207 1년 전 0

ppagse 1년 전 0

ppagse 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말