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

• Problem Link : https://www.acmicpc.net/problem/16947

문제

지하철에서 출발한 역에서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고한다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다. 지하철 2호선과 같은 형태의 노선도가 주어졌을때, 순환선 사이의 거리를 구해본다.

입력

• 첫째 줄, 역의 개수 N이 주어진다.
• N개의 줄에 걸쳐 역과 역을 연결하는 구간의 정보가 주어진다.

출력

총 N개의 정수로, 각 역에서 순환선 사이의 거리를 출력한다.

풀이

역을 노드, 순환선을 그래프의 순환으로 해석하자면 이 문제는 그래프에서 순환을 찾고 모든 노드들을 대상으로 해당 순환까지의 거리를 구하는 문제이다. 순환을 찾는 문제는 DFS로 해결할 수 있다.

순환을 찾는 문제는 16929번 문제를 참고하자.

위 문제와의 차이점은 아래와 같다.

• 순환은 하나 무조건 존재한다.
  - 존재 여부를 찾는 문제가 아니라 순환에 포함된 노드들을 찾아야 한다.
• 모든 노드들로부터 순환까지의 최단 거리를 찾아야 한다.
  - 최단거리는 어떻게? BFS로 구할 수 있다.
  

왜 순환에 포함된 노드들을 알고 있어야하냐면 어떤 역에서 순환까지의 최단 거리를 찾기 위해서는 BFS 탐색으로 거리를 증가시키며 진행을 하나가 내가 순환선의 역 중 하나에 도착했음을 알아야하기 때문이다. 매번 역을 방문할 때마다 내가 서 있는 역이 순환선에 포함된 역인지를 계산하는 것은 시간적, 공간적으로 굉장한 낭비이므로 거리를 찾기 이전에 순환선에 어떤 역들이 들어있는지를 알아야한다.

순환선의 역들을 찾는 것은 위 16929번 문제를 풀어봤다면 굉장히 간단하다. DFS로 내가 방문하는 노들들을 배열에 하나씩 저장해놨다가 순환이 발생했다면 예전에 내가 방문했던 노드부터 현재 내가 서있는 노드까지 슬라이싱을 하면 해당 노드들이 순환에 포함되어 있는 역들이다.

def findRing(route, v, visited):
    global find_route
    if find_route:
        return
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dist[i] = dist[v] + 1
            findRing(route + [i], i, visited)
        if visited[i] and dist[v] >= dist[i] + 2:
            find_route = True
            # print(i, v, route, dist[v], dist[i], dist)
            for j in route[dist[i] : dist[v] + 1]:
                ring[j] = -1
            return route

• 거리 차이가 1이면 바로 직전의 노드로 돌아가는 것도 포함되므로 정상적인 순환 탐색이 아니다. 따라서 직전의 노드는 제외시키면서 순환을 찾기 위해서 거리 차이를 2 이상으로 제한을 두었다.
• find_route라는 부울 변수를 만들어놓은 이유는 순환을 찾았다면 진행중인 재귀들을 더 이상 진행할 필요가 없기 때문에 find_route 부울 변수로 다른 재귀들을 중지시켜준다.
• ring은 순환에 포함된 노드들을 표시해주기 위한 리스트로 기존에 방문했던 노드에서 예전에 내가 방문했던 노드(dist[i])부터 내가 서 있는 노드 (dist[v] + 1, 슬라이싱이므로 +1을 해줘야 현재 노드도 포함)까지 -1로 표현해준다.
  아래 그림을 보면 더 이해하기가 쉽다.
  

이제 우리는 ring이라는 리스트로 내가 방문하는 원소가 순환에 포함된 원소인지 (-1인지) 아니면 포함되지 않은 원소인지를 구별할 수 있다. 출발 노드로부터 순환에 포함된 노드들 중 하나에 방문할 때까지 BFS 함수를 이용해 최단 거리를 구할 수 있다.

# bfs
def bfs(start):
    q = deque()
    q.append([start, 0])

    visited = [False] * n

    while q:
        v, depth = q.popleft()
        if ring[v] == -1:
            return depth

        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                q.append([i, depth + 1])

이제 입력이 들어오면 findRing 함수로 순환에 포함된 원소들을 찾아내고 모든 원소를 출발점으로 해서 BFS로 순환까지의 최단 거리를 구하여 출력하면 문제를 해결할 수 있다.

이 문제는 순환을 찾는 과정에서 DFS, 최단 거리를 찾는 과정에서 BFS를 모두 사용해야 해결할 수 있는 그래프 탐색을 이해하는데 있어 굉장히 좋은 문제라고 할 수 있다.

코드

import sys
from collections import deque

sys.setrecursionlimit(10**6)

input = sys.stdin.readline


find_route = False


def findRing(route, v, visited):
    global find_route
    if find_route:
        return
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dist[i] = dist[v] + 1
            findRing(route + [i], i, visited)
        if visited[i] and dist[v] >= dist[i] + 2:
            find_route = True
            # print(i, v, route, dist[v], dist[i], dist)
            for j in route[dist[i] : dist[v] + 1]:
                ring[j] = -1
            return route


# bfs
def bfs(start):
    q = deque()
    q.append([start, 0])

    visited = [False] * n

    while q:
        v, depth = q.popleft()
        if ring[v] == -1:
            return depth

        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                q.append([i, depth + 1])


# input
n = int(input().rstrip())
graph = [[] * n for _ in range(n)]
for _ in range(n):
    u, v = map(int, input().rstrip().split())
    u, v = u - 1, v - 1
    graph[u].append(v)
    graph[v].append(u)

# find Ring
dist = [-1] * n
dist[0] = 0

visited = [False] * n
ring = [0 for _ in range(n)]
findRing([0], 0, visited)
# print(ring)

# solve
for i in range(n):
    print(bfs(i), end=" ")