글 읽기 - 시간초과.. 뭐부터 해결해야할까요..

yoonsik0926 4년 전 0

시간초과 때문에 통과가 안되는 것같습니다..

bfs를 공부하는 단계라.. 뭐부터 해결하면 될까요..?

from collections import deque

tc = int(input())

def bfs(startNode, totalVisited):
    newVisited = []
    queue = deque()
    queue.append(startNode)
    newVisited.append(startNode)

    while len(queue) > 0:
        nowNode = queue.popleft()
        for node in graph:
            if nowNode[1] == node[0] and node not in newVisited:
                queue.append(node)
                newVisited.append(node)
                totalVisited.append(node)
    return newVisited



for _ in range(tc):
    graph = []
    n = int(input())
    tempList = list(map(int,input().split()))
    for i in range(1, n + 1):
        graph.append([i, tempList[i - 1]])

    visited = []
    answer = []
    for nn in graph:
        if nn not in visited:
            temp = bfs(nn, visited)
            answer.append(temp)
    print(len(answer))

shg9411 4년 전 0

dfs로 풀어보시겠습니까

sait2000 4년 전 0

* 순열 그래프에서는 모든 정점에서 나가는 정점이 딱 한 개 있습니다. 이 한 개의 정점을 찾기 위해 모든 간선을 확인하는 것은 비효율적입니다. 더 효율적인 방법이 필요합니다.

* 리스트에 어떤 원소가 들어있는지 확인하는 연산은 리스트의 모든 원소를 확인해야 하기 때문에 느립니다. 14번 줄이나 32번 줄에서 visited에 간선이 있는지 확인하는 작업에 더 효율적인 방법이 필요합니다.

이 두개는 풀이의 시간복잡도를 바꾸는 문제점입니다. 안 고치면 아마 통과가 안 될 겁니다.

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

문제

문제

출처

ICPC

시간초과.. 뭐부터 해결해야할까요..

yoonsik0926 4년 전 0

shg9411 4년 전 0

sait2000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말