[코테] 백준 그래프 16947번 문제

16947번 : 서울 지하철 2호선

문제 링크

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

문제 설명

서울 지하철 2호선은 다음과 같이 생겼다.

지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.

두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.

지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.

입력

첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.

출력

총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, …, N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

문제풀이

순환선 노선을 산출하는 건 dfs, 순환선과 아닌 노선의 거리를 구하는 건 bfs를 활용하여 문제를 풀이하였다.

# 최대 재귀 횟수를 늘려야 해당 문제에서 recursion error 발생하지 않음
from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 순환선 노선들 산출하는 함수
temp = [0]
def get_circulation_lines(curLine) :
    global circulationLines
    # 현재까지 경로가 아닌 노선들 중에서 다음 노선들만 뽑기
    temp.append(curLine)
    nextLines = [i for i in graph[curLine] if i != temp[-2]]

    for next in nextLines:
        # 이미 순환선 정보를 찾았으면 다음 재귀는 모두 나가기
        if circulationLines :
            break

        # 현재까지 경로에 있던 노선들 중에서 다음 노선이 있을 경우 순환선으로 확인하고 저장
        if next in temp : 
            start = temp.index(next)
            circulationLines = temp[start:].copy()
            return

        # 아닐 경우에는 다음 노선 정보 탐색
        else :
            get_circulation_lines(next)
            temp.pop()

# 현재 노선과 순환선 사이의 거리를 산출하는 함수
def get_distance(curLine) :
    deq = deque([[curLine]])

    while deq :
        temp = deq.popleft()
        nextLines = graph[temp[-1]]

        for next in nextLines :
            # 다음 노선이 순환선이면 현재까지 탐색 길이 리턴
            if next in circulationLines :
                return len(temp)
            # 다음 노선이 현재까지 노선들 중에 없을 경우만 deque에 넣기 
            elif next not in temp : 
                deq.append(temp+[next])

N = int(input())
graph = [[] for _ in range(N+1)]
distances = [0 for _ in range(N+1)]
circulationLines = []

# 양방향 그래프 정보 저장
for _ in range(N) :
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 순환선 노선 산출 (들어가는 숫자는 1~N까지 상관없음)
get_circulation_lines(1)

# 순환선이 아닌 노선들만 거리를 구하기
for i in range(1, N+1) :
    if i not in circulationLines :
        distances[i] = get_distance(i)

# 답안 출력
print(*distances[1:])