[실버 1] 백준 12849 - 본대 산책 (파이썬)

https://www.acmicpc.net/problem/12849

풀이

• 총 8개의 장소(0~7번 정점)로 구성된 캠퍼스가 있고, 하루에 1분씩 이동할 수 있음.
• 이동 가능한 경로는 문제에서 고정되어 있음 (총 12개 간선)
• 0번에서 시작해 정확히 D분 뒤 다시 0번에 도착할 수 있는 모든 경로의 수를 구하는 문제.
• 단, 결과는 10^9 + 7로 나눈 나머지를 출력.

adj = [[] for _ in range(8)]
edge = [ ... ]  # 문제에서 주어진 12개 간선

for a, b in edge:
    adj[a].append(b)
    adj[b].append(a)

먼저 인접 리스트를 정의하고, adj[i]는 i번 정점에서 갈 수 있는 이웃 정점을 리스트로 담고 있다.

양방향 그래프이므로 adj[a].append(b)와 adj[b].append(a)가 모두 필요하다.

dp = [[0] * 8 for _ in range(D + 1)]
dp[0][0] = 1

dp 테이블을 정의하며, dp[i][j]는 i분 후에 j번 정점에 도착하는 경우의 수를 의미한다.

시작점은 0번이므로 dp[0][0] = 1로 초기화 한다.

for i in range(1, D + 1):
    for j in range(8):
        dp[i][j] = 0
        for k in adj[j]:
            dp[i][j] += dp[i - 1][k]
            dp[i][j] %= mod

점화식은 위 코드와 같이 구성한다.

현재 시각 i분일때 정점 j에 도달하는 경우의 수는 j로 들어오는 모든 인접한 정점 k에서 i - 1분에 도착했던 경우의 수의 합이다.

따라서 dp[i][j] = sum(dp[i - 1][k] for k in adj[j])가 된다.

시간복잡도

• 시간 복잡도는 O(D × 8 × deg)
• deg = 평균 연결 정점 수 = 약 2~3 → 충분히 빠름 (D ≤ 100)

코드

# 백준 12849 - 본대 산책
# 분류 : 다이나믹 프로그래밍

D = int(input())
mod = int(1e9 + 7)

adj = [[] for _ in range(8)]

edge = [
    (0, 1),
    (0, 2),
    (1, 2),
    (1, 3),
    (2, 3),
    (2, 4),
    (3, 4),
    (3, 5),
    (4, 5),
    (4, 6),
    (5, 7),
    (6, 7)
]

for a, b in edge :
    adj[a].append(b)
    adj[b].append(a)

dp = [[0] * 8 for _ in range(D + 1)]
dp[0][0] = 1

for i in range(1, D + 1) :
    for j in range(8) :
        dp[i][j] = 0
        for k in adj[j] :
            dp[i][j] += dp[i - 1][k]
            dp[i][j] %= mod

print(dp[D][0])