백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-1967 트리의 지름 편 (python)

문제 살펴보기!!

문제 링크 : https://www.acmicpc.net/problem/1967

반응형

---

솔루션 살펴보기!!

import sys
from collections import defaultdict

def main():
    sys.setrecursionlimit(1000000)  # 재귀 호출 제한을 크게 설정 (큰 트리 처리 가능)

    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    n = int(data[idx])  # 노드 수 입력 받음
    idx += 1

    if n == 1:  # 노드가 1개인 경우, 트리의 지름은 0
        print(0)
        return

    adj = defaultdict(list)  # 인접 리스트로 트리 구조 저장
    for _ in range(n-1):  # 간선 정보 입력
        parent = int(data[idx])
        child = int(data[idx+1])
        weight = int(data[idx+2])
        idx += 3
        adj[parent].append((child, weight))
        adj[child].append((parent, weight))

    def iterative_dfs(start):
        stack = [(start, 0)]  # 스택에 (노드, 거리) 저장
        visited = [False] * (n + 1)  # 방문 체크 리스트
        max_distance = 0  # 최대 거리 초기화
        farthest_node = start  # 가장 먼 노드를 저장할 변수

        while stack:
            node, dist = stack.pop()
            if not visited[node]:  # 방문하지 않은 노드일 경우
                visited[node] = True  # 방문 처리
                if dist > max_distance:  # 더 먼 거리를 찾으면 업데이트
                    max_distance = dist
                    farthest_node = node
                # 인접한 노드를 스택에 추가 (방문하지 않은 노드만)
                for neighbor, weight in adj[node]:
                    if not visited[neighbor]:
                        stack.append((neighbor, dist + weight))
        return farthest_node, max_distance

    # 첫 번째 DFS: 1번 노드에서 가장 먼 노드를 찾음
    u, _ = iterative_dfs(1)
    # 두 번째 DFS: u에서 가장 먼 노드를 찾음 (이때의 거리가 트리의 지름)
    _, diameter = iterative_dfs(u)

    print(diameter)  # 트리의 지름 출력

if __name__ == "__main__":
    main()

---

풀이 전략

이 문제는 트리의 지름을 구하는 문제입니다. 트리의 지름이란 트리에서 두 노드 사이의 가장 긴 경로를 의미합니다. 이를 구하기 위해서는 두 번의 DFS(깊이 우선 탐색)를 이용합니다.

풀이 전략 단계:

1. DFS를 두 번 수행하여 트리의 지름을 계산합니다.
   • 첫 번째 DFS: 임의의 노드(예: 1번 노드)에서 가장 먼 노드를 찾습니다. 이 노드를 트리의 한쪽 끝으로 간주할 수 있습니다.
   • 두 번째 DFS: 첫 번째 DFS에서 찾은 노드에서 다시 DFS를 수행하여 이 노드에서 가장 먼 노드를 찾습니다. 이 때의 거리가 트리의 지름입니다.
2. 트리 구조는 인접 리스트로 표현합니다. 각 노드는 다른 노드와 연결되며, 그 사이에는 가중치가 있습니다.
3. DFS는 스택을 사용한 반복적 탐색으로 구현합니다. 스택을 이용한 DFS는 트리의 깊이가 매우 깊을 때 발생할 수 있는 재귀 호출 깊이 초과 문제를 방지할 수 있습니다.
4. 최종 출력은 트리의 지름입니다.

---

주요 코드 흐름

입력 처리:

• 트리의 노드와 간선 정보를 읽어들여, 인접 리스트를 구성합니다.
• adj는 defaultdict(list)로 각 노드와 연결된 이웃 노드와 가중치를 저장합니다.

adj = defaultdict(list)
for _ in range(n-1):
    parent = int(data[idx])
    child = int(data[idx+1])
    weight = int(data[idx+2])
    idx += 3
    adj[parent].append((child, weight))
    adj[child].append((parent, weight))

DFS를 사용한 탐색:

• DFS를 스택을 사용해 반복적으로 구현합니다. 스택에 (노드, 거리) 형태의 값을 저장하여 탐색 중인 노드와 그 노드까지의 거리를 함께 관리합니다.
• 방문한 노드는 visited 리스트로 체크하고, 탐색 과정에서 현재까지의 최대 거리를 저장하여 트리의 한쪽 끝을 찾습니다.

def iterative_dfs(start):
    stack = [(start, 0)]
    visited = [False] * (n + 1)
    max_distance = 0
    farthest_node = start
    
    while stack:
        node, dist = stack.pop()
        if not visited[node]:
            visited[node] = True
            if dist > max_distance:
                max_distance = dist
                farthest_node = node
            for neighbor, weight in adj[node]:
                if not visited[neighbor]:
                    stack.append((neighbor, dist + weight))
    return farthest_node, max_distance

스택 구조:

• 현재 노드와 그 노드까지의 거리를 스택에 저장한 후, 연결된 이웃 노드를 탐색합니다.
• 방문하지 않은 노드를 스택에 넣고, 탐색을 계속합니다.
• DFS가 끝나면 가장 먼 노드와 그 노드까지의 거리를 반환합니다.

트리의 지름 계산:

• 첫 번째 DFS에서 1번 노드에서 가장 먼 노드를 찾습니다. 이 노드를 u로 둡니다.
• 두 번째 DFS에서는 u에서 가장 먼 노드를 찾고, 이 때의 거리가 트리의 지름입니다

u, _ = iterative_dfs(1)
_, diameter = iterative_dfs(u)

---

코드 흐름 요약

1. 입력 처리: 인접 리스트로 트리의 구조를 저장합니다.
2. DFS 탐색:
   • 첫 번째 DFS로 임의의 노드에서 가장 먼 노드를 찾습니다.
   • 두 번째 DFS로 첫 번째 DFS에서 찾은 노드에서 가장 먼 노드를 찾아 그 거리를 계산합니다.
3. 결과 출력: 트리의 지름을 출력합니다.

이 방식은 트리에서 가장 먼 두 노드를 찾는 가장 효율적인 방법 중 하나입니다. DFS를 두 번만 수행하여 트리의 지름을 구할 수 있으며, 시간 복잡도는 O(N)으로 매우 효율적입니다.

---

주요 개념

1. 그래프 및 트리 데이터 구조

• 트리는 특별한 형태의 그래프입니다. 이 문제에서는 트리의 구조가 주어지며, 트리의 노드와 간선 정보로 트리의 **지름(가장 긴 경로)**을 계산하는 문제입니다.
• 트리의 특징:
  • 트리는 사이클이 없는 연결 그래프입니다.
  • 노드의 개수가 N개일 때, 간선의 개수는 항상 N-1개입니다.
  • 트리의 경로 찾기 문제는 면접에서 자주 등장합니다. 트리의 높이, 지름, 최소 공통 조상(LCA) 등을 묻는 문제가 많습니다.

2. 깊이 우선 탐색 (DFS, Depth-First Search)

• 이 문제에서 트리의 지름을 구하기 위해 DFS(깊이 우선 탐색)를 사용합니다.
• DFS는 그래프나 트리에서 모든 노드를 탐색하는 기본적인 탐색 알고리즘으로, 스택이나 재귀를 사용해 구현할 수 있습니다.
• DFS의 시간 복잡도는 그래프의 노드와 간선의 수에 비례하며, O(N) 시간 복잡도를 가집니다. 이는 트리의 모든 노드를 한 번씩 방문하는 방식으로 지름을 구하는 데 적합합니다.
• 이 문제에서는 반복적 DFS를 사용하여 재귀 호출의 깊이 제한 문제를 피하면서도 효율적으로 탐색을 수행하고 있습니다.

3. 트리의 지름 (Diameter of a Tree)

• 트리의 지름은 두 노드 간의 가장 긴 경로입니다. 이 문제에서는 지름을 구하는 방법으로 DFS를 두 번 사용하는 방법을 적용했습니다.
  1. 첫 번째 DFS: 임의의 노드에서 가장 먼 노드를 찾습니다.
  2. 두 번째 DFS: 첫 번째 DFS에서 찾은 노드에서 가장 먼 노드를 다시 찾습니다.
  • 이 방법은 트리에서 지름을 구하는 효율적인 방법 중 하나로, 면접에서 자주 사용되는 트리 문제 중 하나입니다.

4. 인접 리스트 (Adjacency List)

• 트리(혹은 그래프)를 저장하는 방식 중 하나인 인접 리스트를 사용하였습니다. 인접 리스트는 각 노드에 연결된 이웃 노드들의 리스트를 저장하는 자료구조입니다.
• 이는 메모리 효율적이고, 탐색할 때도 간단하게 이웃 노드로 이동할 수 있습니다. 이 방식은 특히 희소 그래프에서 유리합니다.
• defaultdict(list)를 사용하여 구현하는 방법은 파이썬에서 직관적이고 유연하게 인접 리스트를 관리할 수 있는 좋은 방법입니다.

5. 스택을 이용한 반복적 DFS

• 재귀 대신 스택을 사용하여 반복적으로 DFS를 구현하는 방식입니다. 이 방식은 깊이 제한이 없는 환경에서 재귀 호출로 인한 스택 오버플로우 문제를 방지할 수 있습니다.
• 면접 팁: 면접 중에 재귀 대신 반복문을 사용할 수 있다는 점을 어필하는 것은 좋은 전략입니다. 특히 재귀 호출 제한이 있는 언어에서는 이러한 방법이 유용하게 사용됩니다.

6. 시간 복잡도 분석

• 이 코드의 시간 복잡도는 **O(N)**입니다. DFS는 트리의 각 노드를 한 번씩 방문하므로, N개의 노드와 N-1개의 간선에 대해 선형적으로 탐색합니다.
• 면접에서 시간 복잡도 분석은 매우 중요한 부분입니다. 알고리즘이 얼마나 효율적인지, 그리고 그 효율성을 설명할 수 있는 능력은 면접관이 확인하고자 하는 핵심 사항 중 하나입니다.

---

면접에서 추가적으로 고려할 사항

1. 코드 최적화:
   • 면접관은 코드의 효율성과 최적화를 중요하게 봅니다. 트리의 지름을 구하는 이 알고리즘은 DFS를 두 번만 수행하기 때문에 최적화 측면에서 매우 효율적입니다.
2. 확장 가능한 코드 작성:
   • 코드가 확장 가능하고, 다른 입력이나 추가적인 요구사항이 주어졌을 때 쉽게 변경할 수 있는지 확인합니다.
3. 명확한 설명:
   • 코딩 면접에서는 자신이 작성한 코드의 흐름과 알고리즘 선택 이유를 명확하게 설명하는 것이 중요합니다. 어떤 이유로 특정 알고리즘을 사용했는지, 시간 복잡도는 어떻게 되는지, 경계 조건 처리는 어떻게 했는지 등 면접관에게 논리적으로 설명할 수 있어야 합니다.