[알고리즘/백준] 16947번 : 서울 지하철 2호선(python)

순환선을 찾으려면 dfs를 사용하고
거리를 찾으려면 bfs를 사용하면 된다.

순환선은 dfs를 계속 실행하다가 다시 시작점으로 돌아오면 순환선이라고 한다.
단 조건이 있다. 1-2-1은 순환선이 아니지만 자기 자신으로 돌아온다. 따라서 역을 2개이상 포함해야 한다.

거리는 순환선인 역들은 길이를 0으로 놓고 아닌 역들은 -1로 놓는다. 길이가 0인 역들을 큐에 넣고 거리를 1씩 증가시키면서 -1인 역을 만나면 그 역에 거리를 추가하는 방식으로 풀었다.

import sys
from collections import deque

sys.setrecursionlimit(10 ** 9)


def make_graph(N):
    a = {}
    for i in range(N):
        a[i] = list()

    for _ in range(N):
        i, j = map(int, input().split())
        a[i - 1].append(j - 1)
        a[j - 1].append(i - 1)
    return a


def dfs(start, cnt, now):
    visited[now] = 0
    if start == now and cnt >= 2:
        ans[start] = 0
        return
    for i in graph[now]:
        if visited[i]:
            dfs(start, cnt + 1, i)
        elif i == start and cnt >= 2:
            ans[start] = 0
            return


def bfs():
    q = deque()
    for i in range(N):
        if not ans[i]:
            q.append(i)

    while q:
        now = q.popleft()
        for i in graph[now]:
            if ans[i] == -1:
                q.append(i)
                ans[i] = ans[now] + 1


N = int(input())
graph = make_graph(N)
ans = [-1] * N


for start in range(N):
    visited = [1] * N
    dfs(start, 0, start)
bfs()
print(*ans)