[BOJ] 16947 - 서울 지하철 2호선 (Python)

 

 

아이디어

 

DFS로 사이클을 찾고, BFS로 각 정점과 사이클까지의 거리를 구한다.

 

 

풀이

 

함수 dfs()에서 부모 정점이 아닌 자식 정점을 이미 방문했다면 해당 정점부터 현재 정점까지 사이클이 발생한다.

따라서 해당 정점 번호를 반환하며 현재 정점부터 역으로 해당 정점까지 사이클까지의 거리를 0으로 저장한다.

 

정점과 간선의 개수가 같고 모든 정점을 연결하는 간선이 주어지므로 사이클은 유일하다.

따라서 사이클을 발견한다면 더 이상 사이클을 찾을 필요가 없어 -1을 반환하며 함수를 종료해 나간다.

 

BFS에서 사이클에 포함되는 정점부터 시작해 각 정점과 사이클까지의 거리를 구한 후 출력한다.

 

import sys

sys.setrecursionlimit(10**4)

input = sys.stdin.readline

def solution():

    def dfs(u, prev):
        if visited[u]:
            return u
        visited[u] = 1
        for v in graph[u]:
            if v == prev:
                continue
            r = dfs(v, u)
            if r == -1:
                return -1
            if r > 0:
                D[u] = 0
                stack.append(u)
                if r == u:
                    return -1
                return r
        return 0

    N = int(input())
    graph = [[] for _ in range(N+1)]
    for _ in range(N):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    visited = [0]*(N+1)
    D = [-1]*(N+1)
    stack = []
    dfs(1, 0)
    while stack:
        u = stack.pop()
        for v in graph[u]:
            if D[v] == -1:
                D[v] = D[u]+1
                stack.append(v)
    print(*D[1:])

solution()