[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)
Author And Source
이 문제에 관하여([Python] BOJ 1167 : 트리의 지름 (1)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bae_mung/Python-BOJ-11725트리의-부모-찾기-f1exhsjh저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)