[Python] BOJ 1167 : 트리의 지름 (1)

👉 백준 1167: 트리의 지름 (1)

✔️ 문제 풀이 포인트

from collections import deque

• 시간적으로 효율적인 deque를 이용하여 큐(append, popleft)를 만든다.

def bfs(start):
    check = [-1] * (n + 1) # 방문 체크
    que = deque([start])
    check[start] = 0
    _max = [0, 0]

• 이 문제는 bfs만으로 해결이 가능하다.
• 먼저 방문했는지 체크할 check 리스트를 만들어주고 -1로 초기화를 한다.
  그리고 초기 start 노드를 큐에 넣어주고, check 리스트의 해당 노드 인덱스를 0으로 초기화해준다 (거리를 0으로 초기화하는 것)
• 그리고 _max에 첫번째 인덱스는 해당 노드까지의 최대 거리, 두번째 인덱스는 해당 노드를 의미한다.

while que:
    t = que.popleft()
    for e, w in tree[t]: # e:노드, w:거리
        if check[e] == -1: # 해당 노드에 방문하지 않았다면
            que.append(e) #큐에 노드 추가
            check[e] = check[t] + w # 체크한 곳에 해당 거리 업데이트
            if _max[0] < check[e]: # 최대 거리 노드 갱신
                _max = check[e], e
return _max

• 디큐를 한 노드와 연결된 노드들 중 방문 하지 않은 노드가 있다면
  큐에 인큐하고 해당 노드까지의 거리(기존 거리 + 추가 거리)를 check 리스트에 업데이트 해준다.
• 해당 노드까지의 거리가 여태까지의 최장 거리보다 길다면 최대 거리와 노드를 갱신해준다.

for i in range(n):
    node = list(map(int, input().split()))
    for j in range(1, len(node)-1, 2):
        tree[node[0]].append(node[j:j+2])
        # 처음에는 tree[i]로 해주었더니 틀렸습니다가 나와서 찾아보니
        # 테스트케이스 입력이 1,2,3,4,,, 처럼 순차적으로 주어진다는 조건은 없었다.
        # 따라서 tree[node[0]] 로 수정해주니 간단하게 해결되었다. 

• 1167번 질문을 살펴보면 "4%에서 틀렸습니다." 라는 글이 많이 보이는데, 처음엔 나도 4%에서 틀렸었다.
  해당 질문들의 답변들을 보면 문제에 입력 노드들이 순차적으로 입력된다는 조건이 명시되지 않았고, 따라서 순차적으로 입력받으면 틀리게 된다고 한다.
  그래서 나도 tree[i]에서 tree[node[0]]으로 수정해주니 통과되었다.

dist, node = bfs(1)
dist, node = bfs(node)
print(dist)

• 아무 시작점을 잡고 bfs에 넣어주면 가장 거리가 먼 node가 리턴될 것이고, 리턴된 node를 다시 bfs에 넣어주면 트리의 지름(노드 간 최장거리)가 리턴된다.

✏️ 전체 코드

import sys
from collections import deque
input = sys.stdin.readline

def bfs(start):
    check = [-1] * (n + 1) # 방문 체크
    que = deque([start])
    check[start] = 0
    _max = [0, 0] # maxlen[0]은 해당 노드까지의 최대 거리, maxlen[1]은 해당 노드
    while que:
        t = que.popleft()
        for e, w in tree[t]: # e:노드, w:거리
            if check[e] == -1: # 해당 노드에 방문하지 않았다면
                que.append(e) #큐에 노드 추가
                check[e] = check[t] + w # 체크한 곳에 해당 거리 업데이트
                if _max[0] < check[e]: # 최대 거리 노드 갱신
                    _max = check[e], e
    return _max

n = int(input())
tree = [[] for _ in range(n+1)]
for i in range(n):
    node = list(map(int, input().split()))
    for j in range(1, len(node)-1, 2):
        tree[node[0]].append(node[j:j+2])
        # 처음에는 tree[i]로 해주었더니 틀렸습니다가 나와서 찾아보니
        # 테스트케이스 입력이 1,2,3,4,,, 처럼 순차적으로 주어진다는 조건은 없었다.
        # 따라서 tree[node[0]] 로 수정해주니 간단하게 해결되었다.

dist, node = bfs(1)
dist, node = bfs(node)
print(dist)