[Python] 백준 16947 서울 지하철 2호선

https://www.acmicpc.net/problem/16947

16947번: 서울 지하철 2호선

 

문제 해결

각 점(역)이 cycle 안에 들어가는지 확인해야한다. 이는 DFS를 통해 한바퀴 돌아 다시 출발한 점으로 올 수 있는지 확인한다.

2호선은 순환선이 한 개이지만 문제에서는 두개일 수도 있고 알 수 없다. 그래서 한번 사이클 만들었다고 끝이 아닐 수 있다. (모든 점에서 사이클을 돌려서 안에 있는지 확인해야한다는 점이다.)

cycle안에 있는 점은 거리가 0으로 고정하고 나머지 점들은 cycle에서 얼마나 떨어져있는지 연결고리 카운트를 통해 확인한다.

 

CODE

import sys
input = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(5000)

def cycle(start, now, cnt):
    global is_cycle
    visited[now] = True
    if start == now and cnt>=2:
        is_cycle = True
        return
    for next in graph[now]:
        if not visited[next]:
            cycle(start, next, cnt+1)
        elif next == start and cnt >=2:
            cycle(start,next,cnt)
    return

def distance():
    global check
    q = deque()
    for i in range(1,n+1):
        if cycle_station[i]:
            check[i] = 0
            q.append(i)
    while q:
        now = q.popleft()
        for next in graph[now]:
            if check[next] == -1:
                q.append(next)
                check[next] = check[now] + 1
    print(*check[1:])

if __name__=='__main__':
    n = int(input())
    graph = [[] for _ in range(n+1)]
    cycle_station = [False for _ in range(n+1)]
    check = [-1]*(n+1)
    for _ in range(n):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    for i in range(1,n+1):
        visited = [False for _ in range(n+1)]
        is_cycle = False
        cycle(i,i,0)
        if is_cycle:
            cycle_station[i] = True
    distance()