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

import sys
sys.setrecursionlimit(10000)
def input():
    return sys.stdin.readline().rstrip()

def cycle_check(node,parent):
    if visited[node]:
        return node
    else:
        visited[node] = True
        for next_node in graph[node]:
            if next_node == parent:continue
            return_node = cycle_check(next_node,node)
            if return_node > 0:
                cycle_check_node[node] = True
                if return_node == node:
                    return 0
                else:
                    return return_node
        cycle_check_node[node] = False
        return 0
def dfs(start):
    stack = [(start,0,0)]
    visited = [True for _ in range(N+1)]
    while stack:
        node,parent,dis = stack.pop()

        if cycle_check_node[node]:
            distance[start] = dis
            return
        visited[node] = False

        for next_node in graph[node]:
            if next_node == parent:continue
            if visited[next_node]:
                stack.append((next_node,node,dis+1))



N = int(input())

graph = [[] for _ in range(N+1)]

for _ in range(N):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)


visited = [False for _ in range(N+1)]
cycle_check_node = [False for _ in range(N+1)]
distance = [0 for _ in range(N+1)]

cycle_check(1,0)


for k in range(1,N+1):
    if not cycle_check_node[k]:
        dfs(k)


print(*distance[1:])

  처음 풀이는 생각나는대로 풀었다. 먼저 2가지 함수로 나눠서 했다.

 

처음은 cycle을 체크하는 함수이다. 어느 노드에서든지 시작을 해서, 한번 방문을 했던 노드가 나올때까지

 

부모노드를 제외한 자식노드를 탐색해간다. 그러다보면 cycle의 시작지점을 방문하게 되는데 이때,

 

우리는 해당 node의 번호를 리턴해준다. 그러면 우리는 return 된 값이 0보다 크면

 

이 노드는 사이클에 포함된 노드임을 알 수 있다. 그러므로 return이 된 값이 0보다 크면 cycle임을 체크해주고,

 

시작지점에 도착하면, return 된 node와 값이 같으므로, 그걸로 판별뒤, 그 뒤에는 0을 반환해주면 된다.

 

그러면 우리는 0이 반환이 되면, 해당 노드는 사이클이 아닌것을 알게 된다.

 

이렇게 cycle을 체크한 뒤에

 

dfs를 돌려 cycle을 최초로 만나는 지점까지의 거리를 구해서 저장해주면 된다.

 

 

 

import sys
sys.setrecursionlimit(10000)
def input():
    return sys.stdin.readline().rstrip()

def cycle_check(node,parent):
    if visited[node]:
        return node
    else:
        visited[node] = True
        for next_node in graph[node]:
            if next_node == parent:continue
            return_node = cycle_check(next_node,node)
            if return_node > 0:
                cycle_check_node[node] = True
                distance[node] = 0
                if return_node == node:
                    return 0
                else:
                    return return_node
        cycle_check_node[node] = False
        return 0
def dfs(start,parent):
    if distance[start] != INF:
        return distance[start]
    for next_node in graph[start]:
        if next_node == parent:continue
        distance[start] = min(dfs(next_node,start)+1,distance[start])

    return distance[start]

    



N = int(input())

graph = [[] for _ in range(N+1)]

for _ in range(N):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)


visited = [False for _ in range(N+1)]
cycle_check_node = [False for _ in range(N+1)]
INF = float('inf')
distance = [INF for _ in range(N+1)]

cycle_check(1,0)

for k in range(1,N+1):
    if not cycle_check_node[k] and distance[k] == INF:
        dfs(k,0)

print(*distance[1:])

이 방식은 좀 더 깔끔한 코드이다. 모든 노드들을 dfs를 각각돌리는것이 아닌. cycle인 부분에서부터 1씩 거리를 늘리면서 하나씩 해주는 방식이다.

 

이 방식이 좀 더 깔끔한 방식이다.