【경쟁 프로 전형적인 90문】003의 해설(python)

개요

경쟁 프로 전형 90문 의 해설 기사입니다.
해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다.

※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다.
※★5이상의 문제는 난이도적으로 후회하고 있기 때문에, 투고 시기가 늦어질 가능성이 있습니다. (대신 정중하게 해설 해 주시는 분이라면 꼭 부탁드립니다)

이슈003-Longest Circular Road

문제 개요

그래프 중 가장 경로가 길어지는 도시의 조합을 찾아 +1하여 출력한다.

제약

3 <= N <= 100000 \\
1 <= Ai < Bi <= N \\
(1 <= i <= N-1) \\

・어느 도시간도 이동을 할 수 있어 입력은 모두 정수.

해결 방법

우선,

그래프에서 가장 경로가 길어지는 도시 조합을 찾고,
어째서 상기와 같이 정해지는가 하면, 예를 들면 이하의 화상을 예로 보면 직감적으로 8과 9를 선으로 연결하는 것이 좋다고 알 수 있을까 생각합니다.


여기서, 1로부터의 거리가 가장 먼 것끼리를 연결한다고 하는 생각도 할 수 있습니다만,
이 아이디어에서는 9와 10과 비슷한 것도 후보로 올라가고, 최악의 경우 N 거리도 있을 수 있기 때문에 모두 조사하는 것은 현실적이지 않습니다.

또, (늪에 빠져 있는 분은) 경로를 더함으로써, 최대의 경로가 바뀌는 것은 아닌가? 라고 생각할 수 있지만 이것은
- 도로가 N-1개
- 어느 도시간 이동 가능
라는 조건이 있기 때문에 이번에는 무시할 수 있습니다.

그럼, 최대의 경로가 되는 조합을 구하는 방법입니다만, 이것은 어느 1점으로부터, 가장 거리가 있는 점을 인도해, 그 점으로부터 한층 더 가장 거리가 있는 점을 조사하는 것으로 요구됩니다.
(상기의 화상에서는, 1로부터 가장 깊은 점 8을 구해, 8로부터 다시 탐색을 하는 것으로 구해집니다.)
탐색 방법은 도로에 무게 등도 없기 때문에 폭 우선 탐색으로 좋을까 생각합니다.
(폭 우선 탐색에 대해서는 여기 를 참고해 주십시오.)

구현의 흐름은 다음과 같습니다.
1. 도시 1에서 폭 우선 탐색을 사용하여 가장 먼 도시를 찾습니다.
2. 1에서 구한 도시로부터 폭 우선 탐색을 이용하여 최장이 되는 경로를 구한다.

폭 우선 탐색의 계산량은, 정점수＋변의 수이므로, 이번의 경우는, $N+N-1$,
이것을 2회 실시하기 위해, 합계로 $4N$, 즉 $O(N)$. 이것은 10^5의 순서가 되기 때문에 충분히 시간이 걸립니다.



인용 소스 : 경쟁 프로 전형 90문 Github

구현

answer.py

# キューのインポート
from collections import deque

# 入力の受け取り、道路情報はリストで格納
N = int(input())
G = [[] for _ in range(N)]

for _ in range(N-1):
  A, B = map(int, input().split())
  G[A-1].append(B-1)
  G[B-1].append(A-1)

# 幅優先探索をする関数。今回は１回目の探索で都市が、２回目の探索で長さが必要なため、arrで値を管理した。
def bfs(n):
  Q = deque()
  dist = [-1]*N
  dist[n] = 0
  Q.append(n)

  arr = [0, 0]

  while Q:
    i = Q.popleft()
    for j in G[i]:
      if dist[j] == -1:
        a = dist[i]+1
        dist[j] = a
        Q.append(j)
        if a > arr[1]:
          arr = [j, a]

  return arr

# １回目は０から呼び出し、２回目はbfsからの返り値で呼び出す。
p, dep = bfs(0)
p2, dep2 = bfs(p)

print(dep2+1)

마지막으로

이번 문제는
- 나무 중 가장 긴 경로는 두 번의 탐색으로 구해집니다.
- 폭 우선 탐색의 구현 방법
의 2점이 큰 포인트였습니다.

문제의 해설을 읽어도 다른 사람의 코드를 봐도 확실히 모르는 분
힘에 조금이라도 될 수 있으면 다행입니다.
코드의 개선점이나 그 외, 의견등 있으면, 부담없이 코멘트해 주세요.
또, 이 기사를 읽고 이해할 수 있었던 분은 꼭 LGTM를 눌러 주실 수 있으면 기쁩니다.
(기사 투고의 모티베가 됩니다.)

여기까지 읽어 주셔서 감사합니다.