[Python/파이썬] 백준 16947번: 서울 지하철 2호선

문제

 

풀이

먼저 사이클을 구한다.

사이클은 하나만 존재하고, 길이는 3 이상 이어야 한다.

for i in range(1, n + 1):
    if not visited[i]:
        tmp = []
        if dfs(i, tmp):
            print(cycle)  
            break

def dfs(x, tmp):
    global cycle
    visited[x] = True
    tmp.append(x)
    
    for next in graph[x]:
        if visited[next]:
            if next in tmp:
                if len(tmp[tmp.index(next):]) >= 3:
                    cycle = set(tmp[tmp.index(next):])
                    return True
            continue
        dfs(next, tmp)
        tmp.pop()

 

사이클을 이루는 노드에서 시작하여 깊이를 구해주면 된다.

단 사이클을 이루는 노드의 경우 깊이는 0

d = [-1] * (n + 1)

def setDepth(x, depth):
    if x in cycle:
        d[x] = 0
        depth = 0
    else:
        d[x] = depth
    
    for next in graph[x]:
        if d[next] >= 0:
            continue
        setDepth(next, depth + 1)

setDepth(list(cycle)[0], 0)

 

코드

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def dfs(x, tmp):
    global cycle
    visited[x] = True
    tmp.append(x)
    
    for next in graph[x]:
        if visited[next]:
            if next in tmp:
                if len(tmp[tmp.index(next):]) >= 3:
                    cycle = set(tmp[tmp.index(next):])
                    return True
            continue
        dfs(next, tmp)
        tmp.pop()


n = int(input())
graph = [[] for _ in range(n + 1)]
visited = [False] * (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):
    if not visited[i]:
        tmp = []
        if dfs(i, tmp):
            print(cycle)  
            break

d = [-1] * (n + 1)

def setDepth(x, depth):
    if x in cycle:
        d[x] = 0
        depth = 0
    else:
        d[x] = depth
    
    for next in graph[x]:
        if d[next] >= 0:
            continue
        setDepth(next, depth + 1)

setDepth(list(cycle)[0], 0)

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

 

마무리

지하철을 타지 않아 문제를 꼼꼼히 읽어야 했다...