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

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

문제 요약

• 입력: N개의 역과 N개의 양방향 연결 구간.
• 구조: 순환선(사이클)과 지선(트리 형태).
• 목표: 각 역이 순환선까지의 최소 거리를 계산.

---

해결 방법

1. 순환선(사이클) 찾기:
   • 그래프에서 단 하나의 사이클을 찾습니다.
   • DFS(깊이 우선 탐색)를 사용하여 사이클을 탐지하고, 사이클에 속하는 노드를 기록합니다.
2. 거리 계산:
   • 사이클에 속하는 노드들로부터 BFS(너비 우선 탐색)를 수행하여, 각 노드까지의 최소 거리를 계산합니다.

from collections import deque

def find_cycle(n, adj):
    visited = [False] * (n + 1)
    parent = [0] * (n + 1)
    cycle = []

    def dfs(u, prev):
        nonlocal cycle
        visited[u] = True
        for v in adj[u]:
            if v == prev:
                continue
            if not visited[v]:
                parent[v] = u
                if dfs(v, u):
                    return True
            else:
                # 사이클을 찾았을 때
                if not cycle:
                    # 현재 노드 u부터 v까지의 경로를 사이클로 기록
                    cycle = []
                    temp = u
                    cycle.append(v)
                    while temp != v:
                        cycle.append(temp)
                        temp = parent[temp]
                    return True
        return False

    dfs(1, -1)
    return cycle

def compute_distances(n, adj, cycle_nodes):
    distances = [-1] * (n + 1)
    q = deque()

    # 순환선에 속하는 노드들의 거리는 0
    for node in cycle_nodes:
        distances[node] = 0
        q.append(node)

    # BFS를 통해 거리 계산
    while q:
        current = q.popleft()
        for neighbor in adj[current]:
            if distances[neighbor] == -1:
                distances[neighbor] = distances[current] + 1
                q.append(neighbor)

    return distances[1:]  # 1번부터 출력

def main():
    import sys
    sys.setrecursionlimit(10000)
    input = sys.stdin.readline
    n = int(input())
    adj = [[] for _ in range(n + 1)]
    for _ in range(n):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)

    cycle = find_cycle(n, adj)
    distances = compute_distances(n, adj, cycle)
    print(' '.join(map(str, distances)))

if __name__ == "__main__":
    main()

코드 분석

1. 순환선(사이클) 찾기

def find_cycle(n, adj):
    visited = [False] * (n + 1)
    parent = [0] * (n + 1)
    cycle = []

    def dfs(u, prev):
        nonlocal cycle
        visited[u] = True
        for v in adj[u]:
            if v == prev:
                continue
            if not visited[v]:
                parent[v] = u
                if dfs(v, u):
                    return True
            else:
                # 사이클을 찾았을 때
                if not cycle:
                    # 현재 노드 u부터 v까지의 경로를 사이클로 기록
                    cycle = []
                    temp = u
                    cycle.append(v)
                    while temp != v:
                        cycle.append(temp)
                        temp = parent[temp]
                    return True
        return False

    dfs(1, -1)
    return cycle

• 목적: 그래프에서 순환선을 구성하는 노드들을 찾아내는 함수입니다.
• 방법:
  • *DFS(깊이 우선 탐색)**를 사용하여 사이클을 탐지합니다.
  • visited: 각 노드의 방문 여부를 기록합니다.
  • parent: 각 노드의 부모 노드를 기록하여 사이클을 추적합니다.
  • 사이클이 발견되면, 해당 사이클을 구성하는 노드들을 cycle 리스트에 저장합니다.
• 작동 원리:
  • 노드를 방문하면서 이전 노드(prev)를 제외한 인접 노드를 탐색합니다.
  • 이미 방문한 노드를 다시 방문하게 되면 사이클이 존재함을 의미합니다.
  • 사이클을 발견하면, 현재 노드에서 사이클의 시작 노드까지의 경로를 추적하여 cycle 리스트에 저장합니다.

2. 거리 계산

def compute_distances(n, adj, cycle_nodes):
    distances = [-1] * (n + 1)
    q = deque()

    # 순환선에 속하는 노드들의 거리는 0
    for node in cycle_nodes:
        distances[node] = 0
        q.append(node)

    # BFS를 통해 거리 계산
    while q:
        current = q.popleft()
        for neighbor in adj[current]:
            if distances[neighbor] == -1:
                distances[neighbor] = distances[current] + 1
                q.append(neighbor)

    return distances[1:]  # 1번부터 출력

• 목적: 각 노드가 순환선까지의 최소 거리를 계산합니다.
• 방법:
  • *BFS(너비 우선 탐색)**를 사용하여 거리를 계산합니다.
  • distances: 각 노드의 순환선까지의 거리를 저장하는 리스트입니다. 초기값은 1로 설정합니다.
  • 순환선에 속하는 노드들을 큐에 넣고, 이들의 거리를 0으로 설정합니다.
  • 큐에서 노드를 하나씩 꺼내며 인접 노드의 거리를 업데이트합니다.
• 작동 원리:
  • 순환선에 속하는 모든 노드를 시작점으로 BFS를 수행합니다.
  • BFS를 통해 순환선에 가장 가까운 노드부터 거리를 계산합니다.
  • 이미 거리가 설정된 노드는 다시 방문하지 않습니다.

3. 메인 함수

def main():
    import sys
    sys.setrecursionlimit(10000)
    input = sys.stdin.readline
    n = int(input())
    adj = [[] for _ in range(n + 1)]
    for _ in range(n):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)

    cycle = find_cycle(n, adj)
    distances = compute_distances(n, adj, cycle)
    print(' '.join(map(str, distances)))

if __name__ == "__main__":
    main()

• 작동 순서:
  1. 입력 처리: 역의 개수 N과 연결 정보를 입력받아 인접 리스트(adj)를 구성합니다.
  2. 순환선 찾기: find_cycle 함수를 호출하여 순환선을 구성하는 노드들을 찾습니다.
  3. 거리 계산: compute_distances 함수를 호출하여 각 노드의 순환선까지의 거리를 계산합니다.
  4. 출력: 계산된 거리를 공백으로 구분하여 출력합니다.

---

시간 복잡도 분석

• 순환선 찾기 (find_cycle):
  • DFS를 사용하여 그래프를 탐색하므로, 시간 복잡도는 O(N)입니다.
• 거리 계산 (compute_distances):
  • BFS를 사용하여 모든 노드를 탐색하므로, 시간 복잡도는 O(N)입니다.
• 전체 시간 복잡도: O(N) + O(N) = O(N), 여기서 N은 최대 3,000이므로 효율적입니다.
• 공간 복잡도:
  • 인접 리스트: O(N) 공간을 사용합니다.
  • 방문 배열, 부모 배열, 거리 배열: 각각 O(N) 공간을 사용합니다.
  • 전체 공간 복잡도: O(N)입니다.

---

자료구조 설명

1. 인접 리스트 (adj):
   • 그래프를 효율적으로 표현하기 위해 사용됩니다.
   • 각 노드에 연결된 노드들의 리스트를 저장합니다.
   • 예: adj[1] = [2, 3]은 노드 1이 노드 2와 3에 연결되어 있음을 의미합니다.
2. 큐 (deque):
   • BFS에서 노드를 순차적으로 탐색하기 위해 사용됩니다.
   • popleft()와 append() 연산이 O(1) 시간에 수행됩니다.
3. 리스트 (visited, parent, distances):
   • 각 노드의 상태를 기록하기 위해 사용됩니다.
   • visited: DFS에서 노드의 방문 여부를 기록합니다.
   • parent: DFS에서 노드의 부모를 기록하여 사이클을 추적합니다.
   • distances: BFS에서 각 노드의 순환선까지의 거리를 기록합니다.