태야

<내 코드>

from collections import deque


def bfs(s):
    q = deque()
    visited = [0 for _ in range(n+1)]

    q.append(s)
    visited[s] = 1

    while q:
        x = q.popleft()

        for i in tree[x]:
            if visited[i] == 0:
                visited[i] = 1
                result[i] = result[x] + 1
                q.append(i)


n = int(input())
a, b = map(int, input().split())
m = int(input())
tree = [[] for _ in range(n+1)]
result = [0 for _ in range(n+1)]

for _ in range(m):
    x, y = map(int, input().split())
    tree[x].append(y)
    tree[y].append(x)

bfs(a)
if result[b] != 0:
    print(result[b])
else:
    print(-1)

BFS로 그래프를 탐색하며 현재 탐색하는 노드와 연결된 노드에 현재 노드 값의 +1을 한다. 즉, 연결된 노드를 이동하는 것을 의미한다.

이런 식으로 모든 노드들을 탐색을 마치면 찾고자 하는 노드의 인덱스의 값을 출력해주면 된다.

<내 코드>

import sys
sys.setrecursionlimit(10**6)

n = int(input())
in_order = list(map(int, input().split()))
post_order = list(map(int, input().split()))

pos = [0]*(n+1)
for i in range(n):
    pos[in_order[i]] = i

# 전위 순회
def divide(in_start, in_end, p_start, p_end):

    if(in_start > in_end) or (p_start > p_end):
        return

    parents = post_order[p_end]  # 후위순회에서 부모노드 찾기
    print(parents, end=" ")

    left = pos[parents] - in_start  # 왼쪽인자 갯수
    right = in_end - pos[parents]  # 오른쪽인자 갯수

    divide(in_start, in_start+left-1, p_start, p_start+left-1)  # 왼쪽 노드
    divide(in_end-right+1, in_end, p_end-right, p_end-1)  # 오른쪽 노드


divide(0, n-1, 0, n-1)

후위 순회에서 부모 노드를 찾아 중위 순회에서 기준으로 삼아 왼쪽, 오른쪽 나눈다. 그리고 왼쪽 자식 트리 노드, 오른쪽 자식 트리 노드를 순회하며 앞의 과정을 반복한다.

<내 코드>

T = int(input())

for _ in range(T):
    N, M = map(int, input().split())
    for _ in range(M):
        a, b = map(int, input().split())
    print(N-1)

일단 문제에서 모든 곳이 연결된 그래프이기 때문에, 최소 비행기 수는 (나라 수 - 1)이다. 왜냐하면 모든 나라를 여행하는 것이라 시작점을 어디든지 될 수 있다. 즉, 한중일 세 나라가 있다면 한국 - 일본, 한국 - 중국 이런식으로 시작점을 맘대로 정할 수 있기 때문이다.

<내 코드>

import sys
sys.setrecursionlimit(100000)


def dfs(start, tree, weight, ck):
    # ck로 루트1번에서 시작한 건지, 최장길이 노드를 루트로 한건지 판단
    if ck == 1:
        weight[1] = 0  # 루트 1번 노드 가중치 0으로 설정

    for node, w in tree[start]:
        if(weight[node] == 0):
            weight[node] = weight[start] + w  # 현재 가중치 + 다음 노드와 가중치
            dfs(node, tree, weight, ck)


n = int(sys.stdin.readline())
tree = [[] for _ in range(n+1)]
# 입력 값 tree 생성
for _ in range(n-1):
    p_node, c_node, w = map(int, sys.stdin.readline().split())
    tree[p_node].append((c_node, w))
    tree[c_node].append((p_node, w))

weight1 = [0 for _ in range(n+1)]  # 루트1로부터 길이를 저장
dfs(1, tree, weight1, 1)  # 루트 1 시작점으로 해 가장 먼 노드를 찾음


# 찾은 가장 먼 노드를 시작 노드로 탐색
# 최장경로 노드에서 다시 DFS를 통해 트리지름구하기
start_node = weight1.index(max(weight1))
weight2 = [0 for _ in range(n+1)]

dfs(start_node, tree, weight2, 2)

print(max(weight2))

같은 코드로 python3, pypy3로 제출했을 때 시간 차이가 5000ms 정도 차이가 났다...

확실히 DFS는 시간이 많이 걸리는 것 같다. 파이썬은 테스트에서 되도록이면 BFS를 이용하는 게 좋지 않을까 생각한다.

알고리즘 이해

: 일단 트리의 지름을 구하려면 가장 끝 노드끼리 거리가 될거다. 거기서도 가장 큰 가중치(거리)를 가지는 것이 최종 지름이 된다.

1. 루트 1번을 시작으로 해서 가장 긴(먼 거리)에 있는 즉, 가중치가 큰  끝 노드를 DFS 탐색으로 찾는다.

2. 찾은 끝 노드를 다시 루트노드로 설정해 DFS 탐색을 한다.

3. 탐색하며 더한 가중치 값들 중 최댓값을 출력하면, 트리의 지름이 된다.