16947: 서울 지하철 2호선

• 초반에 생각했던 알고리즘

import sys
from collections import deque

def check_cycle(curr, start, depth):
    visit[curr] = True
    for i in range(len(adjacent[curr])):
        if not visit[adjacent[curr][i]]:
            check_cycle(adjacent[curr][i], start, depth+1)
        elif adjacent[curr][i] == start and depth >= 2: #cycle이 형성된 경우
            cycle.add(adjacent[curr][i])
            return

def distance(curr, depth):
    visit[curr] = True
    for i in range(len(adjacent[curr])):
        if adjacent[curr][i] in cycle:
            print(depth+1, end=" ")
            return
        elif not visit[adjacent[curr][i]]:
            distance(adjacent[curr][i], depth+1)


N = int(input())
adjacent = [[] for _ in range(N+1)]
for i in range(N):
    tmp = list(map(int, sys.stdin.readline()[:-1].split(' ')))
    adjacent[tmp[0]].append(tmp[1])
    adjacent[tmp[1]].append(tmp[0])

cycle = set()
for x in range(1, N+1):
    visit = [False] * (N+1)
    check_cycle(x, x, 0)

for x in range(1, N+1):
    if x not in cycle:
        visit = [False] * (N+1)
        distance(x, 0)
    else:
        print("0", end=" ")

• 처음에 작성한 코드 (Recursion error, 시간 초과 발생)
• check_cycle()을 통해 먼저 cycle이 생기는 node들을 찾고 cycle (set) 에 저장해놓음
• 그 후 distance()를 통해 다시 dfs를 순회하면서 cycle에 있는 최단거리 (depth+1) 를 출력

-> distance를 구하는 과정에서, dfs 대신 bfs를 통해 한번에 최단거리를 찾도록 바꾸어줌

-> 또한, cycle에 포함된 node에서부터 distance를 구하는 방식으로 변경

-> 그리고, 기존에는 for문에서 인접리스트 원소에 접근할 때 인덱스 기반으로 접근했었는데, 그것보다는 python만의 방식으로 접근하는 게 시간도 더 적게 걸리는듯

import sys
from collections import deque
sys.setrecursionlimit(100000)

def check_cycle(curr, start, depth):
    visit[curr] = True
    for next in adjacent[curr]:
        if not visit[next]:
            check_cycle(next, start, depth+1)
        elif next == start and depth >= 2: #cycle이 형성된 경우
            cycle.add(next)
            return

def distance():
    dist_ans = [-1] * (N+1)
    queue = deque([])

    for i in range(1, N+1):
        if i in cycle: #cycle에 속하는 node에서 bfs 시작
            queue.append(i)
            dist_ans[i] = 0

    while queue:
        curr = queue.popleft()
        for next in adjacent[curr]:
            if dist_ans[next] == -1:
                queue.append(next)
                dist_ans[next] = dist_ans[curr] + 1
    
    for i in range(1, N+1):
        print(dist_ans[i], end=' ')



N = int(input())
adjacent = [[] for _ in range(N+1)]
for i in range(N):
    tmp0, tmp1 = map(int, sys.stdin.readline()[:-1].split(' '))
    adjacent[tmp0].append(tmp1)
    adjacent[tmp1].append(tmp0)

cycle = set()
for x in range(1, N+1):
    visit = [False] * (N+1)
    check_cycle(x, x, 0)

distance()

• distance()를 bfs 방식으로 변경
• dist_ans list를 이용하여 거리를 저장해둔 후, 한번에 출력하도록 변경