[Python] 16947 서울 지하철 2호선

💻 문제 정의

다음 지하철 2호선과 같은 형태의 그래프가 주어졌을 때, 각 구간과 순환 구간 사이의 거리를 구하는 문제이다.

 

💡 접근 및 설계

그래프에서 사이클이 발생하는 구간을 구하고 해당 구간에 포함된 노드들의 거리는 0이 된다. 이후 사이클이 아닌 노드에 대해서 사이클이 포함된 노드까지의 거리를 구하면 된다.

문제에서 노드의 개수 N개, 그리고 간선의 수도 N개이다. 따라서 해당 그래프에는 반드시 하나의 사이클이 존재한다. DFS로 탐색 시작 노드와 현재 방문 노드를 비교하며 같다면, 사이클이 발생한다고 할 수 있다. 이후 사이클이 발생하지 않는 노드에 대해서 BFS를 이용하여 거리를 구할 수 있을것이다.

✏️ 알고리즘 풀이

cycle = [False] * (N+1)

def dfs(node, start, cnt):
    # 현재 방문 점과 시작점이 같고, 지금까지 방문한 노드 수가 2개 이상이면
    if node == start and cnt >= 2:
        cycle[node] = True
        return

    visited[node] = True

    for ix in graph[node]:
        if not visited[ix]:
            dfs(ix, start, cnt+1)
        elif ix == start and cnt >= 2:
            dfs(ix, start, cnt)
            
for i in range(1, N+1):
    visited = [False] * (N+1)
    dfs(i, i, 0)

방문 노드와 탐색 시작노드, 그리고 지금까지 방문한 노드의 개수 정보를 통해 탐색을 시작한다. 방문하지 않은 노드로 탐색을 이어나갈땐 방문 노드 개수를 증가시켜주고, 다음 방문 예정인 노드가 시작점과 일치하다면 지금 정보 그대로 탐색을 이어나간다. 최종적으로 현재 방문 노드와 시작 노드가 같고, 방문한 노드의 개수가 2개 이상이라면 해당 노드는 사이클이 발생한다.

def bfs():
    Q = deque()
    for i in range(1, N+1):
        if cycle[i]:
            Q.append(i)
            visited[i] = 0

    while Q:
        curr = Q.popleft()

        for ix in graph[curr]:
            if visited[ix] == -1:
                visited[ix] = visited[curr]+1
                Q.append(ix)
                
visited = [-1] * (N+1)
bfs()

이후 사이클이 존재하는 노드로부터 사이클이 존재하지 않는 노드로 BFS를 이어가며 거리를 구한다. 최종적으로 visited리스트에 거리 정보가 저장될 것이다.

🗒️ 최종 제출 코드

# 16947 서울 지하철 2호선

import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)

def dfs(node, start, cnt):
    # 현재 방문 점과 시작점이 같고, 지금까지 방문한 노드 수가 2개 이상이면
    if node == start and cnt >= 2:
        cycle[node] = True
        return

    visited[node] = True

    for ix in graph[node]:
        if not visited[ix]:
            dfs(ix, start, cnt+1)
        elif ix == start and cnt >= 2:
            dfs(ix, start, cnt)

def bfs():
    Q = deque()
    for i in range(1, N+1):
        if cycle[i]:
            Q.append(i)
            visited[i] = 0

    while Q:
        curr = Q.popleft()

        for ix in graph[curr]:
            if visited[ix] == -1:
                visited[ix] = visited[curr]+1
                Q.append(ix)
            
N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

cycle = [False] * (N+1)

for i in range(1, N+1):
    visited = [False] * (N+1)
    dfs(i, i, 0)

visited = [-1] * (N+1)
bfs()

for i in range(1, N+1):
    print(visited[i], end=' ')

❓ 또 다른 풀이

사이클이 발생하는 구간을 찾는 또 다른 방법이 있다. 각 노드의 차수를 이용한 방법이다.

1. 각 노드의 차수를 구한다. 리프 노드의 차수는 1이다.
2. 차수가 1인 노드에 대해 DFS를 이어나간다. 리프 노드를 제거한다.
3. 모든 리프노드를 제거한 후에도 차수가 1보다 큰 노드들은 사이클이 발생한다.

차수(degree) : 한 노드에 존재하는 간선의 개수. 따라서 차수가 1이면 해당 노드는 간선이 한 개 존재. 따라서 leaf_node가 될 것이고, 차수가 2 이상이라면 leaf_node가 아니다. 모든 leaf_node를 제거한 후에도 간선의 개수가 2개 이상이라면, 해당 노드는 사이클에 존재한다고 볼 수 있다.

cycle = [True] * (N+1)
def find_cycle():
    Q = deque()
    for i in range(1, N+1):
        if degree[i] == 1:
            Q.append(i)

    while Q:
        curr = Q.popleft()
        cycle[curr] = False

        for next in graph[curr]:
            degree[next] -= 1
            if degree[next] == 1:
                Q.append(next)

차수를 이용해 leaf_node를 제거하고, 남아있는 노드들은 사이클을 구성함을 이용한 풀이 방법이다.

🗒️ 최종 제출 코드 (2)

# 16947 서울 지하철 2호선

import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)

def find_cycle():
    Q = deque()
    for i in range(1, N+1):
        if degree[i] == 1:
            Q.append(i)

    while Q:
        curr = Q.popleft()
        cycle[curr] = False

        for next in graph[curr]:
            degree[next] -= 1
            if degree[next] == 1:
                Q.append(next)

def bfs():
    Q = deque()
    for i in range(1, N+1):
        if cycle[i]:
            Q.append(i)
            visited[i] = 0

    while Q:
        curr = Q.popleft()

        for ix in graph[curr]:
            if visited[ix] == -1:
                visited[ix] = visited[curr]+1
                Q.append(ix)

N = int(input())
graph = [[] for _ in range(N+1)]
degree = [0] * (N+1)
for _ in range(N):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    degree[a] += 1
    degree[b] += 1

cycle = [True] * (N+1)
find_cycle()

visited = [-1] * (N+1)
bfs()

for v in visited[1:]:
    print(v, end=' ')

---

💭 오늘의 회고

그래프에서 사이클을 찾는 후 탐색을 통해 거리를 구한다는 생각은 했으나, 사이클을 찾는 방법을 몰라 고전했던 문제였다.

Union-Find를 활용한 분리 집합으로 사이클을 찾아낼 수 있을거라 생각하였으나 Union-Find는 단순 사이클 존재 여부만 판단할 수 있고, 어떤 노드들이 사이클을 구성하는지는 알아낼 수가 없다. 따라서 Union-Find는 적합한 풀이 방법이 아니었다.

DFS를 이용하여 사이클을 찾은다음 BFS로 사이클 - 노드간의 거리를 구하는 방식이 정석 풀이인 줄 알았으나 각 노드의 차수(degree)를 이용해 leaf_node를 제거하여 사이클을 찾아내는 것이 정석인 문제였다. 시간도 훨씬 빠르고 구현도 DFS보다 쉬운 것 같다.