글 읽기 - 파이썬(pypy) 시간초과

shkorea1004 2년 전 0

dfs,bfs 모두 시간초과가 나서 답답한 마음에 질문드려요

혹시 제 코드에서 시간초과를 줄일 방법이 있을까요??

import sys
from collections import deque


def getInput():
    N, M = map(int, sys.stdin.readline().split())
    arr = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        arr[b].append(a)
    return N, arr


def dfs(temp, A, arr, visited):
    for i in A:
        if i not in temp:
            temp.append(i)
    else:
        for i in A:
            if not visited[i]:
                visited[i] = True
                dfs(temp, arr[i], arr, visited)


def bfs(temp, A, arr, visited):
    A = deque(A)
    first = 0
    while A:
        first = A.popleft()
        temp.append(first)
        visited[first] = True
        for i in range(len(arr[first])):
            if not visited[arr[first][i]]:
                A.append(arr[first][i])
    

def solution():
    N, arr = getInput()
    maxNum = 0
    ans = []
    for i in range(1, N + 1):
        temp = [i]
        visited = [False] * (N + 1)
        bfs(temp, arr[i], arr, visited)
        # dfs(temp, arr[i], arr, visited)
        if len(temp) > maxNum:
            ans = []
            maxNum = len(temp)
            ans.append(i)
        elif len(temp) == maxNum:
            ans.append(i)
    for i in ans:
        sys.stdout.write(str(i) + " ")


solution()

mugglim 2년 전 1

안녕하세요!

위의 BFS 함수에서 특정 line만 개선하면 될 것 같습니다.

1. 매번 BFS의 시작을 i가 아닌 first(0)로 하는 이유.

2. visited[arr[first][i] ]가 False인 경우 바로 True로 처리하지 않은 이유.

추가로 코드 첨부합니다.
만약 코드에 문제가 있거나 문의사항이 있으시다면 대댓 부탁드립니다.

# 수정 코드
def bfs(temp, i, arr, visited):
    queue = deque([i])
    visited[i] = True
    while queue:
        curr = queue.popleft()
        temp.append(curr)
        for next in arr[curr]:
            if visited[next] == False:
                visited[next] = True
                queue.append(next)

shkorea1004 2년 전 1

아 매번 0부터 돌아서 시간초과났던 것이였네요 ㅜㅜ

답변 정말 감사드립니다. 도움이 많이됬습니다.

좋은하루보내세요!!

mugglim 2년 전 0

네! 즐거운 하루 되시길 바랍니다!

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

문제

문제

출처

ICPC

파이썬(pypy) 시간초과

shkorea1004 2년 전 0

mugglim 2년 전 1

shkorea1004 2년 전 1

mugglim 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말