백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-17073 나무 위의 빗물 편 (python)

문제 살펴보기

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

반응형

---

솔루션 살펴보기

import sys
from sys import stdin


def main():
    sys.setrecursionlimit(1 << 25)
    
    def input():
        return sys.stdin.read()

    data = input().split()
    idx = 0

    N = int(data[idx])
    W = int(data[idx + 1])
    idx += 2

    # 트리의 인접 리스트 초기화
    adj = [[] for _ in range(N + 1)]
    degrees = [0] * (N + 1)

    for _ in range(N - 1):
        u = int(data[idx])
        v = int(data[idx + 1])
        adj[u].append(v)
        adj[v].append(u)
        degrees[u] += 1
        degrees[v] += 1
        idx += 2

    # 루트 노드는 1번
    # 리프 노드는 degree가 1이고, 노드가 1번이 아닌 노드
    leaf_count = 0
    for node in range(2, N + 1):
        if degrees[node] == 1:
            leaf_count += 1

    # 평균 Pi 계산
    if leaf_count == 0:
        average_Pi = 0.0
    else:
        average_Pi = W / leaf_count

    # 소수점 아래 10자리까지 출력
    print("{0:.10f}".format(average_Pi))

if __name__ == "__main__":
    main()

---

코드 흐름 및 풀이 전략 설명

이 코드는 주어진 입력으로부터 트리를 구성하고, 그 트리의 리프 노드 개수를 바탕으로 어떤 값을 계산하는 문제를 해결하는 코드입니다. 이 코드는 트리 문제에서 흔히 사용되는 기법인 "리프 노드의 개수 계산"을 활용하며, 특정한 가중치를 리프 노드에 나누어주는 문제에서 사용될 수 있습니다. 여기서 사용된 전략을 단계별로 설명하겠습니다.

1. 재귀 제한 설정 및 입력 처리

• sys.setrecursionlimit(1 << 25)를 통해 재귀 호출 한도를 높입니다. 이 부분은 트리 문제에서 재귀를 많이 사용할 때 스택 오버플로우를 방지하기 위해 설정합니다. 이 문제에서는 재귀를 사용하지 않지만, 준비된 설정이라고 볼 수 있습니다.
• input()은 표준 입력을 처리하는 함수로, sys.stdin.read()를 사용하여 입력을 한 번에 읽고, 이를 공백으로 나누어 처리하는 방식입니다. 입력 데이터는 트리 구조를 나타내는 간선 정보와 트리와 관련된 가중치 정보를 포함합니다.

2. 트리의 초기화 및 간선 연결

• N은 노드의 개수, W는 주어진 가중치 값을 나타냅니다.
• adj는 트리의 인접 리스트를 나타내며, 각 노드에 연결된 다른 노드들을 저장합니다. degrees 배열은 각 노드의 차수(즉, 노드에 연결된 간선의 수)를 기록합니다.
• 루프를 통해 간선 정보를 입력받아 인접 리스트와 차수 배열을 채워줍니다.

3. 리프 노드 계산

• 트리의 루트는 1번 노드라고 가정하고, 루트 노드를 제외한 나머지 노드들 중 차수가 1인 노드를 리프 노드로 정의합니다. 차수가 1이라는 것은 다른 노드와 연결된 간선이 하나밖에 없다는 의미로, 이는 리프 노드를 의미합니다.
• 2번 노드부터 차수를 검사하여 리프 노드를 세는 과정을 진행합니다.

4. 평균 Pi 계산

• 문제에서 리프 노드에 가중치를 나누어주어야 하므로, W 값을 리프 노드의 개수로 나누어 각 리프 노드가 가지는 평균 가중치를 계산합니다.
• 리프 노드가 하나도 없으면 평균은 0이므로 이를 처리하는 조건문이 있습니다.
• 결과는 소수점 아래 10자리까지 출력됩니다.

5. 출력

• 최종적으로, 계산된 평균 가중치를 소수점 아래 10자리까지 출력하는 방식으로 문제를 마무리합니다.

코드 면접 시 활용할 수 있는 주요 개념

1. 트리 구조의 이해:
   • 이 문제는 트리를 그래프 형태로 구현하고 리프 노드를 찾아 처리하는 문제입니다. 트리 문제는 알고리즘 면접에서 매우 빈번히 등장하는 주제입니다. 특히 DFS(깊이 우선 탐색), BFS(너비 우선 탐색), 동적 프로그래밍을 이용한 트리 문제는 FAANG 면접에서 자주 나옵니다.
2. 인접 리스트로 그래프 표현:
   • 트리를 인접 리스트로 표현하는 방법은 그래프 탐색에서 가장 기본적이고 효율적인 방법입니다. 노드의 연결 상태를 쉽게 관리할 수 있고, 트리나 그래프 문제에서 일반적으로 사용됩니다.
3. 리프 노드의 정의:
   • 리프 노드는 차수가 1인 노드입니다. 이를 통해 트리의 말단 노드를 식별하고, 특정 계산에 활용하는 방식은 여러 문제에서 공통으로 사용할 수 있는 중요한 개념입니다. 특히 리프 노드를 처리하는 문제는 동적 프로그래밍과 자주 연결됩니다.
4. 소수점 출력:
   • 면접에서 부동 소수점 연산의 정확성에 대한 문제는 중요한 주제입니다. "{0:.10f}".format(value)와 같은 방식으로 소수점 자리를 고정하는 기법은 부동 소수점과 관련된 오류를 피하는 방법 중 하나입니다.
5. 입력 최적화 및 시간 복잡도 관리:
   • sys.stdin.read()를 사용한 전체 입력 처리와 split()을 통해 한 번에 데이터를 처리하는 방식은 많은 입력이 주어질 때 효율성을 높이는 기법입니다. 트리 문제는 보통 O(N)의 시간 복잡도를 가지기 때문에, 이러한 최적화는 면접에서 중요한 포인트가 될 수 있습니다.