[ 백준 ] 12928 트리와 경로의 길이 ( Python )

BOJ 12928

문제 이해 먼저 문제를 정확히 이해하는 것이 중요합니다.

• 트리의 노드 개수는 N개여야 합니다.
• 길이가 2인 단순 경로의 개수는 S개여야 합니다.
• 단순 경로란 같은 정점을 두 번 이상 반복하지 않는 경로를 의미합니다.
• 경로의 방향은 상관없습니다. 즉, A-B-C와 C-B-A는 같은 경로로 간주합니다.

접근 방법 이 문제를 해결하기 위해서는 동적 계획법(Dynamic Programming)을 활용할 수 있습니다. 트리의 노드 개수와 경로의 개수를 변수로 하는 2차원 DP 배열을 정의하고, 이를 통해 문제를 해결할 수 있습니다.

DP[i][j]는 i개의 노드로 이루어진 트리에서 길이가 2인 단순 경로의 개수가 j개인 경우의 수를 의미합니다. 이를 활용하여 문제의 조건을 만족하는 트리의 존재 여부를 판단할 수 있습니다.

풀이 과정

1. 입력 받기:

   • N과 S를 입력 받습니다.
   • DP 배열을 초기화합니다. (크기: 55 x 1010)

2. 함수 정의 (f(n, c)):

   • n: 현재 고려 중인 노드의 개수
   • c: 현재까지 구한 길이가 2인 단순 경로의 개수
   • 종료 조건:
     • n이 0이고 c가 s와 같으면 조건을 만족하는 트리가 존재하므로 1을 출력하고 프로그램을 종료합니다.
     • n이 0이거나 이미 방문한 상태(dp[n][c]가 True)이거나 c가 s보다 크면 함수를 종료합니다.
   • 현재 상태를 방문 처리합니다. (dp[n][c] = True)
   • 1부터 n까지의 노드 개수에 대해 반복합니다.
     • 다음 경로 개수 next_c를 계산합니다. (next_c = c + i * (i + 1) // 2)
     • next_c가 s 이하이면 f(n - i, next_c)를 재귀적으로 호출합니다.

3. 메인 로직:

   • n이 1보다 크면 f(n - 2, 0)를 호출하여 트리의 존재 여부를 판단합니다.
   • 조건을 만족하는 트리가 없으면 0을 출력합니다.

Why? 이 문제를 해결하기 위해 동적 계획법을 사용한 이유는 다음과 같습니다:

• 트리의 노드 개수와 경로 개수에 따라 중복되는 하위 문제들이 발생합니다.
• 이러한 중복 계산을 피하고 효율적으로 문제를 해결하기 위해 DP를 활용합니다.
• DP를 통해 이미 계산한 결과를 저장하고 재사용함으로써 시간 복잡도를 줄일 수 있습니다.

이 문제에서는 트리의 노드 개수를 하나씩 줄여가면서 경로의 개수를 계산하고, 이를 DP 배열에 저장합니다. 이렇게 함으로써 중복된 계산을 피할 수 있고, 주어진 조건을 만족하는 트리의 존재 여부를 효율적으로 판단할 수 있습니다.

전체 코드 보기

import sys
input = sys.stdin.readline
n, s = map(int, input().split())
dp = [[False] * 1010 for _ in range(55)]
def f(n, c):
    if n == 0 and c == s:
        print("1")
        sys.exit(0)
    if n == 0 or dp[n][c] or c > s:
        return
    dp[n][c] = True
    for i in range(1, n + 1):
        next_c = c + i * (i + 1) // 2
        if next_c <= s:
            f(n - i, next_c)
if n > 1:
    f(n - 2, 0)
print("0")

이 문제를 통해 동적 계획법의 활용 방법과 트리의 구조에 대해 이해할 수 있었습니다. 주어진 조건을 만족하는 트리의 존재 여부를 판단하기 위해 DP를 효과적으로 사용하는 방법을 배울 수 있었습니다.

앞으로도 다양한 알고리즘 문제를 풀어보면서 문제 해결 능력을 키워나가시길 바랍니다. 감사합니다!