[백준] 1167 트리의 지름

문제

---

풀이 과정

1) 문제 이해 및 접근

최초 문제를 접하였을때, 두개의 노드에서 가장 먼 거리를 구해야 하므로 DFS 탐색을 하여 가장 먼 거리를 구하는 방식으로 생각했습니다.

출발 노드가 어디냐에 따라 먼 거리가 달라질 수 있으므로 완전 탐색 방식으로 접근했습니다.

 

그러나 모든 노드를 완전 탐색하여야 했기 때문에 시간 초과가 발생했습니다.

시간 초과 문제를 해결하기 위해 고민 한 결과 모든 노드를 출발지로 선택하여 DFS 탐색을 해햐하는것이 비효율적이라 판단됬습니다.

 

고민한 결과 트리의 지름을 구하려할때 트리의 특징을 발견했습니다.

어떠한 노드에서 최초 1회 탐색을 하였을때, 가장 멀리 있는 노드의 번호를 알아내고 그 노드로 다시 한번 DFS 탐색을 하였습니다.

이러한 방식을 이용하면 트리에서 가장 긴 지름을 구할 수 있고, DFS 탐색을 단 두개의 노드에서만 진행하면 되었기에 시간 단축을 할 수 있었습니다.

2) 알고리즘

• DFS (깊이 우선 탐색)

3) 풀이 코드

사용 언어 - Python

최초 접근 방식 풀이 - 시간 초과

"""
초기에 노드들마다 가장 먼거리를 찾아서 가장 먼곳을 찾으려 했으나
시간 초과 발생
"""
def dfs(start):
    global answer

    visited = [False] * (V+1)
    distance = [0] * (V+1)
    stack = [start]
    
    while stack:
        node = stack.pop()
        if not visited[node]:
            visited[node] = True
            for e in linked[node]:
                if not visited[e[0]]:
                    distance[e[0]] = e[1] + distance[node]
                stack.append(e[0])
    
    answer = max(answer, max(distance))


V = int(sys.stdin.readline())
linked = [[] for _ in range(V+1)]

for i in range(V):
    value = list(map(int, sys.stdin.readline().split()))
    for j in range(1, len(value)-1, 2):
        linked[value[0]].append((value[j], value[j+1]))

answer = 0

for i in range(1, V+1):
    dfs(i)

print(answer)

 

최종 코드 - 시간 초과 문제 해결

import sys
sys.stdin = open('input.txt')


def dfs(node, distance):                # 노드 번호 / 현재까지 지름
    global longest, start               # 전역 변수 사용 위함

    if distance > longest:              # 지금까지 거리가 가장 긴 지름보다 큰 경우
        longest = distance              # 지름 값 갱신
        start = node                    # 가장 긴 지름의 도착 노드 번호

    for e in linked[node]:              # 현재 노드와 연결된 노드들 순환
        if not visited[e[0]]:           # 아직 방문하지 않은 노드인 경우
            visited[node] = 1           # 방문 처리
            dfs(e[0], distance+e[1])    # 다음 탐색 (재귀)


V = int(sys.stdin.readline())           # 노드의 개수
linked = [[] for _ in range(V+1)]       # 트리의 연결 관계
longest = 0                             # 가장 먼 거리를 저장하는 변수
start = 0                               # 트리 1회 탐색 후 가장 먼 거리에 있는 노드의 번호

for i in range(V):
    value = list(map(int, sys.stdin.readline().split()))    # 입력받은 노드의 연결 관계
    for j in range(1, len(value)-1, 2):                     # 1번 인덱스부터 2개씩, 연결된 노드 번호 / 거리 의 값이 들어와서 그 개수만큼 반복
        linked[value[0]].append((value[j], value[j+1]))     # 튜플 형식으로 (연결된 노드 번호, 노드까지의 거리)

for e in [start, start]:        # 초기 랜덤한 노드에서 탐색 시작 / 초기 탐색에서 찾은 가장 멀리 있는 노드에서 다시 탐색
    visited = [0] * (V+1)       # 방문 리슽트 초기화
    dfs(start, 0)               # 출발 노드 번호 / 현재까지 지름

print(longest)                  # 출력

---

결과 및 학습한 내용

1) 어려웠던 내용

노드의 개수가 많아서 모든 노드를 출발점으로 DFS 탐색을 하게 되면 시간 초과가 발생한다는것을 인지하지 못했습니다.

문제 해결을 고민하는 과정에서 트리의 특성을 파악하는데 어려움을 겪었습니다.

2) 새롭게 학습한 내용

문제의 난이도가 상승함에 따라 제한 시간을 더 고려할 필요가 있다는것을 알게 되었습니다.

---

문제 링크

- https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다