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

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

풀이

각 역과 순환선 사이의 거리를 구하는 문제다. 역이 순환선 위에 존재한다면 거리는 0으로 계산한다. 그래프 문제이므로 순환선 = 사이클을 구하고 사이클 위에 있지않은 노드의 거리를 구해야한다. 사이클은 DFS를 이용, 거리를 구할 때는 사이클 위에 있는 노드부터 시작하여 BFS를 이용해 해결할 수 있다. 사용되는 변수는 다음과 같다.

N: 노드의 개수
graph: 인접 노드 
-> graph[a] = b: b는 a의 인접노드다.
cycle[N]: False라면 노드 N은 사이클에 속하지 않음 / True라면 노드 N은 사이클에 속함
visited[N]: False라면 노드 N은 방문하지 않았음 / True라면 노드 N은 방문한 노드임
cycle_find: 사이클을 찾았는지 확인하는 boolean variable

DFS: 사이클 찾기

사이클은 그래프 이론에서 닫힌 구역이며 시작 지점과 끝 지점이 일치해야 한다. 단, 시작지점으로 돌아올 때 까지의 거리가 2보다 커야한다.

위 그림에서 보듯이 A - B - A 일 때는 사이클의 시작부터 끝까지 거리는 2이며 이는 사이클이 아니다. A - B - C - D 는 사이클의 시작부터 끝까지 거리는 3이며 이는 사이클이다.

구현 방법은 기본적으로 DFS 방법을 사용한다. 문제를 해결하기 위해서는 단순히 사이클의 유무를 찾는것이 아니라 사이클 위에 있는 노드를 모두 구해야한다.

def dfs(target, cnt, start)
# target: 현재 탐색할 노드
# cnt: 거리
# start: 시작 위치

사이클을 찾아야하므로 시작 위치와 거리를 저장하는 파라미터가 필요하다.

if visited[target]:
	if cnt >= 3 and target == start:
    	cycle_find = True
        return target
    else:
    	return -1

먼저 target 노드에 방문했는지 확인한다. 일반적인 DFS라면 방문한 노드는 다시 방문하지 않지만 사이클은 다시 방문한 노드가 결국 마지막 노드임을 확인해야한다. 이때 시작 노드와 같은지, 또한 시작과 끝의 거리가 2보다 큰지를 확인한다. 이 조건을 만족할 경우 이는 사이클이고 이때 사이클의 시작 노드를 반환한다.

visited[target] = True

for node in graph[target]:
	cycle_start_node = dfs(node, cnt + 1, start)
    if cycle_start_node != -1:
    	cycle[target] = True
        if target == cycle_start_node:
        	return -1
        else:
        	return cycle_start_node    

dfs가 -1이 아닌 특정 노드값을 반환할 경우 사이클을 찾았으며 현재 노드는 사이클에 포함됨을 의미한다. 결과적으로 사이클을 찾았다면 사이클 위에 존재하는 모든 노드를 발견할 수 있다.

BFS: 순환선과의 거리 구하기

사이클 위에 있는 노드로부터 서서히 확장해나가는 방식으로 각 노드의 거리를 구할 수 있다. 기본적으로 사이클 위에 존재하는 노드는 순환선과의 거리가 0이다. 이때 사이클을 벗어나 다른 노드를 탐색하게 되면 거리를 1씩 늘여간다.

코드

from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def dfs(target, cnt, start):
    global cycle_find
    # 다시 방문
    if visited[target]:
        # a -> b -> a is not cycle
        # a -> b -> c -> a is cycle
        # 다시 방문 했으나 그때 거리가 3이상일시
        if cnt >= 3 and target == start:
            # this is cycle start node!
            cycle_find = True
            return target
        # this case, a -> b -> a!
        # or... only visited node
        else:
            return -1

    # target에 방문
    visited[target] = True

    for node in graph[target]:
        # 방문하지 않았다면
        cycle_start_node = dfs(node, cnt + 1, start)

        if cycle_start_node != -1:
            cycle[target] = True
            # 사이클 백트래킹 끝
            # 시작지점까지 되돌아옴
            if target == cycle_start_node:
                return -1
            else:
                return cycle_start_node
    return -1

# Initial
N = int(input())
graph = [[] for _ in range(N + 1)] # 1 ~ N node
cycle = [False for _ in range(N+1)]
visited = [False for _ in range(N+1)]
answer = [0 for _ in range(N+1)] # distance answer
cycle_find = False

for _ in range(N):
    a, b = map(int, input().split())
    # Undirected Graph
    graph[a].append(b)
    graph[b].append(a)

# 1. Find the Cycle Using DFS
for i in range(1, N+1):
    cycle = [False for _ in range(N+1)]
    visited = [False for _ in range(N+1)]
    dfs(i, 0, i)
    if cycle_find:
        break
# print('[DEBUG] cycle:', cycle)

# 2. Get the minimum distance Using BFS
queue = deque()

for i in range(1, N+1):
    if cycle[i]:
        # If node is in cycle, distance = 0
        # BFS를 이용해 거리를 구할것이므로
        # 사이클에 속하는 노드부터 뻗어나감
        queue.append(i)
        answer[i] = 0
    else:
        answer[i] = -1

while queue:
    v = queue.popleft()
    for node in graph[v]:
        # node is not in CYCLE
        # 첫 갱신
        if answer[node] == -1:
            queue.append(node)
            # 뻗어나가면서 거리가 1씩 늘어남
            answer[node] = answer[v] + 1

# Answer
print(' '.join(map(str, answer[1:])))

재귀함수를 사용하기 때문에 sys.setrecursionlimit()로 깊이의 한계를 늘여줘야 한다.

참고

아래는 참고한 홈페이지/자료입니다. 감사합니다.

https://baby-ohgu.tistory.com/35