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

문제 살펴보기!!

 

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

반응형

---

솔루션 살펴보기!!

import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    idx = 0

    # 노드의 수 N과 루트 노드 R을 입력받음
    N = int(data[idx]); idx += 1
    R = int(data[idx]); idx += 1

    # 인접 리스트 초기화 (노드 번호가 1부터 시작한다고 가정)
    adj = [[] for _ in range(N + 1)]

    # N-1개의 간선 정보 입력받기
    for _ in range(N - 1):
        a = int(data[idx]); idx += 1
        b = int(data[idx]); idx += 1
        d = int(data[idx]); idx += 1
        adj[a].append((b, d))
        adj[b].append((a, d))

    # 현재 노드, 부모 노드, 줄기의 합을 초기화
    current = R
    parent = -1
    stem_sum = 0
    giga_node = -1

    # 기가 노드(giga_node)와 줄기의 합(stem_sum)을 찾는 과정
    while True:
        # 현재 노드의 자식 노드들 찾기 (부모 노드는 제외)
        children = [(v, d) for v, d in adj[current] if v != parent]
        if len(children) >= 2:
            # 자식이 두 개 이상이면 기가 노드로 설정
            giga_node = current
            break
        elif len(children) == 1:
            # 자식이 하나이면 줄기에 포함하고 다음 노드로 이동
            child, d = children[0]
            stem_sum += d
            parent = current
            current = child
        else:
            # 자식이 없으면 현재 노드를 기가 노드로 설정
            giga_node = current
            break

    # 기가 노드의 최대 분기 합(max_branch_sum) 계산
    # 기가 노드가 리프 노드인 경우
    if (len(adj[giga_node]) == 1 and giga_node != R) or (N == 1 and giga_node == R):
        max_branch_sum = 0
    else:
        # 기가 노드의 자식들 중 부모가 아닌 노드들에 대해 DFS 수행
        stack = []
        for v, d in adj[giga_node]:
            if v != parent:
                stack.append((v, giga_node, d))
        
        max_branch_sum = 0
        while stack:
            node, parent_node, sum_so_far = stack.pop()
            children = [(v, d) for v, d in adj[node] if v != parent_node]
            if not children:
                # 리프 노드에 도달했을 때 최대 합 업데이트
                if sum_so_far > max_branch_sum:
                    max_branch_sum = sum_so_far
            else:
                # 자식 노드들에 대해 계속 탐색
                for child, d in children:
                    stack.append((child, node, sum_so_far + d))

    # 결과 출력
    print(stem_sum, max_branch_sum)

if __name__ == "__main__":
    main()

---

이 코드는 트리에서 루트 노드에서 **기가 노드(Giga Node)**까지의 "줄기(stem)" 길이와, **기가 노드 이후 분기(branch)**에서의 최대 길이를 계산하는 문제를 해결합니다. 트리는 간선으로 연결된 노드들로 이루어진 그래프이며, 이 문제는 특정 조건을 만족하는 기가 노드를 찾고, 그 이후 분기되는 최대 길이를 계산하는 문제입니다.

주요 용어

• 기가 노드(Giga Node): 자식 노드가 두 개 이상인 첫 번째 노드입니다. 기가 노드까지는 트리가 단일 경로로 이어지며, 그 이후로 트리가 분기됩니다.
• 줄기(stem): 루트 노드에서 기가 노드까지의 경로 길이입니다.
• 분기(branch): 기가 노드 이후로 뻗어 나가는 경로들입니다.

풀이 전략

1. 입력 처리 및 인접 리스트 생성:
   • 트리의 노드 개수 N과 루트 노드 R이 입력으로 주어집니다.
   • 인접 리스트(adj)는 각 노드에 연결된 노드들과 그 간선의 가중치(거리)를 저장하는 방식으로 트리를 표현합니다. 이때 트리의 간선 정보는 양방향이므로, 각 노드에 대해 양쪽 노드를 모두 리스트에 추가합니다.
2. 기가 노드와 줄기(stem) 길이 찾기:
   • 루트 노드 R에서 시작하여, 단일 경로로 이어지는 노드를 추적합니다.
   • 노드를 탐색하면서, 자식 노드가 두 개 이상이면 그 노드를 기가 노드로 간주하고 탐색을 멈춥니다.
   • 기가 노드 이전까지의 경로를 줄기로 간주하여 그 길이를 stem_sum에 더해줍니다.
   • 자식 노드가 없으면 해당 노드를 리프 노드로 간주하고 기가 노드로 설정합니다.
3. 분기(branch) 길이 계산:
   • 기가 노드 이후의 노드들을 탐색하여, 최대 길이를 구합니다.
   • DFS(깊이 우선 탐색)을 이용해 기가 노드에서 시작하여 자식 노드로 뻗어나가는 경로들을 모두 탐색합니다.
   • 각 리프 노드까지의 경로 중 가장 긴 경로를 max_branch_sum으로 계산합니다.
4. 최종 결과 출력:
   • 줄기의 길이와 기가 노드 이후 분기의 최대 길이를 출력합니다.

주요 코드 흐름

입력 처리 및 인접 리스트 초기화

N = int(data[idx]); idx += 1
R = int(data[idx]); idx += 1
adj = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a = int(data[idx]); idx += 1
    b = int(data[idx]); idx += 1
    d = int(data[idx]); idx += 1
    adj[a].append((b, d))
    adj[b].append((a, d))

기가 노드와 줄기 찾기

current = R
parent = -1
stem_sum = 0
giga_node = -1
while True:
    children = [(v, d) for v, d in adj[current] if v != parent]
    if len(children) >= 2:
        giga_node = current
        break
    elif len(children) == 1:
        child, d = children[0]
        stem_sum += d
        parent = current
        current = child
    else:
        giga_node = current
        break

 

• 루트 노드에서 출발하여 자식이 한 개 있는 노드를 계속 따라가며 줄기의 길이를 stem_sum에 누적합니다.
• 자식 노드가 두 개 이상인 첫 번째 노드를 기가 노드로 설정하고 탐색을 종료합니다.

분기(branch)에서의 최대 길이 계산

if (len(adj[giga_node]) == 1 and giga_node != R) or (N == 1 and giga_node == R):
    max_branch_sum = 0
else:
    stack = []
    for v, d in adj[giga_node]:
        if v != parent:
            stack.append((v, giga_node, d))
    max_branch_sum = 0
    while stack:
        node, parent_node, sum_so_far = stack.pop()
        children = [(v, d) for v, d in adj[node] if v != parent_node]
        if not children:
            if sum_so_far > max_branch_sum:
                max_branch_sum = sum_so_far
        else:
            for child, d in children:
                stack.append((child, node, sum_so_far + d))

 

 

• 기가 노드가 리프 노드일 경우 max_branch_sum은 0으로 설정됩니다.
• 그렇지 않으면 DFS를 사용하여 기가 노드 이후의 각 경로를 탐색하고, 그 중 가장 긴 경로를 max_branch_sum에 저장합니다.

---

풀이 전략 요약

• 트리에서 경로 탐색: 루트 노드에서부터 자식 노드가 두 개 이상 나오는 지점까지 탐색하여 줄기 길이를 계산합니다.
• 기가 노드 이후 최대 분기 길이 계산: 기가 노드 이후의 경로를 DFS로 탐색하여 가장 긴 경로를 찾습니다.
• DFS 활용: 깊이 우선 탐색을 사용해 트리의 리프 노드까지 탐색하고, 그 중 가장 긴 경로를 계산합니다.

---

주요 개념

이 코드에서 다루고 있는 문제는 트리 자료구조를 기반으로 하고 있으며, 여러 가지 중요한 개념들이 면접에서 자주 질문되는 주제와 밀접하게 관련되어 있습니다. 트리, 깊이 우선 탐색(DFS), 인접 리스트, 그리고 시간 복잡도 분석 등 다양한 개념을 이해하고 설명할 수 있어야 합니다. 면접에서 이 코드와 관련된 주요 개념은 다음과 같습니다:

1. 트리(Tree) 자료구조

• 트리의 정의: 트리는 계층적 구조를 갖는 비순환 그래프입니다. 트리에서 각 노드는 하나의 부모를 가지며, 루트 노드에서 시작해 리프 노드로 끝납니다.
• 노드 간의 관계: 이 문제에서는 루트 노드에서 시작해 기가 노드까지 이어지는 경로(줄기)와, 기가 노드 이후에 분기된 경로들(분기)을 탐색합니다.
• 트리 탐색: 트리의 경로를 찾거나 탐색하는 데는 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS)이 주로 사용됩니다.

면접 팁: 트리의 특성, 트리의 순회 방식(DFS, BFS), 그리고 이들을 적용하는 방법을 알고 있어야 합니다. 트리에서 노드 간의 관계를 파악하고 경로를 탐색하는 방법에 익숙해야 합니다.

2. 인접 리스트(Adjacency List)

• 그래프 표현 방식: 트리나 그래프를 저장할 때는 인접 리스트 또는 인접 행렬을 사용할 수 있습니다. 이 문제에서는 인접 리스트를 사용해 각 노드와 그에 연결된 노드, 그리고 가중치(간선의 거리)를 저장합니다.
• 효율성: 인접 리스트는 공간 효율성이 좋고, 노드의 연결 정보를 빠르게 탐색할 수 있기 때문에 트리나 그래프에서 자주 사용됩니다.

면접 팁: 인접 리스트와 인접 행렬의 차이점을 이해하고, 각각의 장단점을 설명할 수 있어야 합니다. 이 문제에서 왜 인접 리스트가 사용되었는지 설명하는 것도 중요합니다.

3. 깊이 우선 탐색(DFS)

• DFS(Depth-First Search): 이 코드에서는 DFS를 사용해 기가 노드 이후의 경로들을 탐색하고, 그 중 가장 긴 경로를 찾습니다. DFS는 재귀적으로 또는 스택을 사용해 구현할 수 있습니다.
• 리프 노드 탐색: DFS는 기가 노드 이후 분기된 경로에서 리프 노드에 도달할 때까지 탐색을 진행하며, 경로의 가중치를 누적해 최대 값을 찾습니다.

면접 팁: DFS의 시간 복잡도(O(V + E), V: 노드 수, E: 간선 수)를 알고, DFS가 트리에서 어떻게 적용되는지 설명할 수 있어야 합니다. 또한 DFS와 BFS의 차이점과 사용 시점을 이해하고 있어야 합니다.

4. 루트 노드와 기가 노드의 개념

• 루트 노드: 트리의 시작점이며, 이 문제에서는 트리의 첫 번째 노드 R이 루트입니다. 루트에서 출발해 기가 노드를 찾아가는 경로를 줄기(stem)라고 부릅니다.
• 기가 노드: 자식 노드가 두 개 이상인 첫 번째 노드로, 이 노드를 기준으로 트리의 구조가 분기됩니다. 기가 노드는 이 문제에서 중요한 전환점입니다.

면접 팁: 면접관이 트리에서 중요한 노드(예: 루트, 리프, 기가 노드 등)의 역할을 질문할 수 있습니다. 각 노드의 특성과 역할을 설명할 수 있어야 합니다.

5. 스택(Stack) 사용

• 스택을 이용한 DFS 구현: 이 코드에서는 DFS를 스택을 사용해 반복문으로 구현했습니다. 스택은 탐색 중 이전에 방문한 노드를 기억해, 노드를 다시 방문하지 않도록 하는 데 유용합니다.
• 재귀적 DFS와 스택 기반 DFS: DFS는 재귀적으로 구현할 수도 있지만, 면접에서는 재귀를 사용하지 않고 스택을 이용한 DFS 구현을 요구할 수 있습니다. 스택을 사용한 DFS 구현은 반복문으로 동작하며, 재귀 호출로 인한 스택 오버플로우 문제를 방지할 수 있습니다.

면접 팁: DFS를 스택으로 구현하는 방법과 재귀로 구현하는 방법을 모두 이해하고 있어야 합니다. 면접에서 스택 기반 DFS 구현을 요구할 수 있기 때문에, 이를 코드로 작성하는 연습을 해야 합니다.

6. 시간 복잡도(Time Complexity)

• 트리 탐색 시간 복잡도: 이 코드에서 트리를 탐색하는 과정은 트리의 모든 노드를 한 번씩 방문하고, 각 간선을 한 번씩 처리하므로 시간 복잡도는 O(N)입니다. 여기서 N은 트리의 노드 수입니다.
• 효율성: 트리 탐색과 경로 계산이 효율적으로 이루어지며, 트리 구조의 특성상 중복 탐색이 발생하지 않도록 부모 노드를 제외하는 방식으로 자식 노드 탐색을 제한합니다.

면접 팁: 코드를 작성한 후에는 항상 시간 복잡도와 공간 복잡도를 분석할 수 있어야 합니다. 트리의 특성상 DFS가 O(N) 복잡도를 가지며, 이는 트리 문제에서 매우 중요한 점입니다.

7. 문제 분해 및 해결 전략

• 문제 분해: 문제를 두 가지로 분리하여 해결합니다. 첫째, 루트에서 기가 노드까지의 경로(줄기)를 찾고, 둘째, 기가 노드에서 분기된 경로들 중 가장 긴 경로(분기)를 찾는 것입니다.
• 탐색 방향 설정: 각 단계에서 탐색하는 노드를 추적하면서 부모-자식 관계를 적절히 처리하고, 조건에 따라 탐색 방향을 결정하는 논리를 갖추고 있습니다.

면접 팁: 면접에서 복잡한 문제를 해결할 때는 문제를 작은 단위로 분해하는 것이 중요합니다. 문제의 각 부분을 어떻게 나누고 해결했는지, 그리고 전체적인 해결 전략을 설명할 수 있어야 합니다.

8. 예외 처리와 경계 조건

• 특수 경우 처리: 트리의 노드가 하나밖에 없거나, 기가 노드가 루트 노드일 경우에도 정상적으로 동작해야 합니다. 이러한 경계 조건은 코드에서 명확히 처리되어야 합니다.
• 기가 노드가 리프 노드일 때: 기가 노드 이후에 더 이상 분기가 없으면 분기의 최대 길이는 0이 됩니다.

면접 팁: 코드를 작성할 때 경계 조건과 예외 처리를 빠뜨리지 않고 구현하는 것이 중요합니다. 면접에서는 "이 경우는 어떻게 처리하나요?"라는 질문이 나올 수 있으므로, 예외 처리에 대한 설명을 할 수 있어야 합니다.