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

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

16947번: 서울 지하철 2호선

DFS를 활용하여 풀이한 문제입니다. 먼저, 싸이클을 찾기 위해 DFS가 필요로 한데 아무 정점을 시작으로 DFS 진행하는데 이전 노드로만 되돌아가지 않게 진행을 합니다. 이렇게 하면 한쪽 방향으로만 DFS가 가능하게 됩니다. 한쪽 방향으로 탐색하다 방문한 정점을 또 만나게 된다면 그 정점이 싸이클의 시작정점이 되게 됩니다. 시작 정점을 찾은 순간 flag에 싸이클의 시작을 설정해주고 리턴해주게 되면 다시 싸이클의 시작정점을 마주치기 전까지 만난 정점들은 모두 싸이클에 포함된 정점들을 찾을 수 있습니다. 

 

그 다음으로는 싸이클로부터의 거리를 구해야하는데 이것도 DFS로 계산해주었습니다. 그래프에 연결된 정점의 길이가 1인 정점을 시작으로 거리를 계산해주면 싸이클을 만나는 경로에 있는 정점들도 자동으로 거리를 계산할 수 있습니다.

 

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 8)

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

graph = defaultdict(list)

n = int(input())

for _ in range(n):
    v1, v2 = tuple(map(int, input().split()))
    graph[v1].append(v2)
    graph[v2].append(v1)

visited = [False] * (n + 1)
in_cycle = [False] * (n + 1)


# 순환으로부터의 거리
dist = [0] * (n + 1)


cycle_start = -1

def getCycle(cur, prev):
    global cycle_start

    # 싸이클을 찾은 경우이므로 true를 리턴한다.
    if visited[cur]:
        cycle_start = cur
        return True

    flag = False
    visited[cur] = True

    for next_node in graph[cur]:
        # 이전으로만 돌아가지 않게 한다.
        if next_node != prev:
            flag = flag or getCycle(next_node, cur)

    in_cycle[cur] = flag

    # 싸이클로 다시 돌아왔으면
    if cur == cycle_start:
        return False

    return flag


def getDist(cur):
    #print(cur)
    if in_cycle[cur]:
        return 1

    visited[cur] = True

    ret = -1

    for next_node in graph[cur]:
        if not visited[next_node]:
            ret = getDist(next_node)
            # 싸이클로부터의 거리를 찾은 경우에는 더이상 탐색하지 않는다.
            if ret > 0:
                dist[cur] = ret
                return ret + 1

    return ret



getCycle(1, -1)

visited = [False] * (n + 1)

for i in range(1, n + 1):
    if len(graph[i]) == 1:
        visited = [False] * (n + 1)
        getDist(i)

print(*dist[1:])

 

DFS + DFS

 

두번째 풀이입니다. 거리 계산 시간을 BFS로 바꾸어 거리 계산을 조금 더 효울적으로 바꾸었습니다. 기존의 방식은 테케 5번 같은 경우 1번노드로 시작할 때와 2번 노드로 시작할 때 3번 노드의 거리를 중복으로 계산해주게 됩니다. 이를 피하기 위해 BFS로 거리를 계산해주었습니다. 싸이클에 포함된 아무 정점을 시작으로 BFS를 진행하면서 싸이클에 포함된 정점들은 거리가 0이 되고 싸이클에 포함되어 있지 않은 정점이라면 현재 정점을 기준으로 +1을 해주면 싸이클로부터의 거리를 구할 수 있습니다.

 

import sys
from collections import defaultdict, deque

sys.setrecursionlimit(10 ** 8)

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

graph = defaultdict(list)

n = int(input())

for _ in range(n):
    v1, v2 = tuple(map(int, input().split()))
    graph[v1].append(v2)
    graph[v2].append(v1)

visited = [False] * (n + 1)
in_cycle = [False] * (n + 1)


# 순환으로부터의 거리
dist = [0] * (n + 1)


cycle_start = -1

def getCycle(cur, prev):
    global cycle_start

    # 싸이클을 찾은 경우이므로 true를 리턴한다.
    if visited[cur]:
        cycle_start = cur
        return True

    flag = False
    visited[cur] = True

    for next_node in graph[cur]:
        # 이전으로만 돌아가지 않게 한다.
        if next_node != prev:
            flag = flag or getCycle(next_node, cur)

    in_cycle[cur] = flag

    # 싸이클로 다시 돌아왔으면
    if cur == cycle_start:
        return False

    return flag


def calDist():
    start = -1
    for i in range(1, n + 1):
        if in_cycle[i]:
            start = i
            break
    visited = [False] * (n + 1)

    q = deque([(start, 0)])
    visited[start] = True

    # 싸이클에 포함된 정점을 시작으로 거리를 계산한다.
    while q:
        cur, w = q.popleft()

        dist[cur] = w

        for next in graph[cur]:
            if not visited[next]:
                visited[next] = True
                # 싸이클에 포함되어 있으면 거리는 0이다.
                if in_cycle[next]:
                    q.append((next, 0))
                # 싸이클에 포함되어 있지 않으면 1을 늘려준다.
                else:
                    q.append((next, w + 1))

getCycle(1, -1)
calDist()

print(*dist[1:])

 

DFS + BFS