junyub2   2달 전

제가 작성한 코드에서 이중반복문으로 인해서 시간초과가 난다는 것과 시간복잡도 O(n^2)을 갖는다는것은 대강 알고있고, 이보다 작은 시간복잡도를 사용해서 풀어야 한다는 것을 알고있지만 어떻게 계산을 하는것인지 잘 모르겠어서 질문드립니다.

import sys
from collections import defaultdict
n, m, k, x = map(int, sys.stdin.readline().split())
dic = defaultdict(list)

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    dic[a].append(b)
    dic[b].append(a)

visited= [0]*(n+1)

def bfs(x):
    queue = [x]
    check = set()
    idx = []
    while queue:
        x = queue.pop(0)
        check.add(x)
        for i in dic[x]:
            if i not in check:
                queue.append(i)
                check.add(i)
                visited[i] = visited[x] + 1
    for i in range(len(visited)):
        if visited[i] == k:
            idx.append(i)
    return idx

ans = bfs(x)
if len(ans) > 0:
    for i in ans:
        print(i)
else:
    print(-1)

시간이 얼마나 걸리는지 대략적으로 알 수 있는 방법같은게 있을까요?

그리고 해당 문제에서는 범위를 정해주지만 보통 저희가 사용하는 프로그램에서는 범위가 정해져있지 않은데

time()을 사용해서 시간이 얼마나 걸리나 보는게 의미가 있을까요?

보기 편하시라고 아래 써놨습니다

n 최대범위 300,000

m 최대범위 1,000,000

k 최대범위 300,000

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