글 읽기 - 어느 부분에서 시간이 많이 걸리는 걸까요..?

codren 2년 전 1

제 코드를 수행하면 6000ms 정도까지 나옵니다.

하지만 이 분의 코드 (다른 분의 코드)를 보면 100ms 수행시간이 나오는데

dfs 와 bfs 를 이용하는 비슷한 원리같은데 어디서 이렇게 차이가 많이 나는 걸까요??

import sys
from collections import deque
sys.setrecursionlimit(10**5)

# 순환선을 구하기 위한 dfs
def dfs(v,route,depth):
    global start
    visited[v] = True
    depth += 1
    route.append(v)

    for u in graph[v]:
        if start == u and depth >= 3:
            cycle.extend(route)

    for u in graph[v]:
        if visited[u] == False:
            dfs(u,route,depth)
            route.pop()

# 순환선까지의 최단 거리를 구하기 위한 bfs
def bfs(v,depth):
    queue = deque()
    visited[v] = True
    queue.append((v,depth))

    while(queue):
        v,depth = queue.popleft()

        for u in graph[v]:
            if u in cycle:
                return depth+1
            if visited[u] == False:
                queue.append((u,depth+1))
                visited[u] = True


n = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
cycle = []
res = [0] * (n+1)

# 노선 정보 입력 받기
for _ in range(n):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

# 순환선 구하기 위한 dfs for문
for i in range(1,n+1):
    if cycle:
        break
    
    visited = [False] * (n+1)
    start = i
    dfs(start,[],0)

# 순환선에 속하는 역은 제외
not_cycle = set(i for i in range(1,n+1)) - set(cycle)

# 순환선에 속하지 않는 역에서만 bfs 수행
for i in not_cycle:
    visited = [False] * (n+1)
    res[i] = bfs(i,0)

for i in range(1,n+1):
    print(res[i],end=' ')

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

문제

문제

출처

ICPC

어느 부분에서 시간이 많이 걸리는 걸까요..?

codren 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말