[白俊/python 3]16947ソウル地下鉄2号線

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

に答える

これは各駅と環状線の間の距離を求める問題です.局が環状線の上に存在する場合、距離はゼロです.グラフィックの問題なので,ループ線=ループを求め,ループ上にないノードの距離を求めなければならない.ループは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は、1周期の始点から終点までの距離が3であり、これは1周期である.
実装方法は基本的に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:ループ線との距離を求める

各ノードの距離は,ループ中のノードから徐々に拡張することによって求めることができる.基本的に,ループ上に存在するノードとループ線との距離はゼロである.このとき、ループを離れて他のノードを探索すると、距離が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