백준 15587 Cow at Large (Gold) 파이썬 풀이

 

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

15587번: Cow at Large (Gold)

요즘 유사코 실~골 div를 돌고 있는데, 여기는 문제 난이도가 적당하고 굉장히 맛있는 것 같다.

다양한 풀이가 존재하는 것 같은데, 나는 dfs + tree dp + 약간의 그리디로 풀었다.

 

Bessie가 있는 K를 루트로 하는 트리를 생각해보자.

예제에서 주어진 트리이다.

만약 6, 7노드에 farmer가 있다고 해도, bessie는 첫 턴에 바로 2로 탈출을 할 수 있다. 그렇기에 2에는 무조건 farmer가 있어야한다. 2에 farmer가 있으면, bessie가 첫 턴에 할 수 있는 행동은 노드 3으로 내려가는 것 밖에 없다. 만약 6에 farmer가 있다 하더라도, 첫 턴에는 4까지 밖에 못 오기에, bessie는 5로 도망칠 수 있다. 그래서 예제 입력에서는 모든 리프 노드에 farmer가 존재햐아하고, 답이 3으로 나온다.

 

dp(i) = 리프노드에서 노드 i로 갈때의 최소 거리 라 하자.

그럼 bessie가 k에서 노드 i로  dp(i)보다 빨리 갈 수 있으면, i를 최소로 가는 리프에 farmer를 설치해봤자 의미가 없다. 하지만 그 반대라면? i를 최소로 가는 리프에 farmer를 설치한다면, i보다 밑에 있는 노드를 고려해줄 필요가 없다. 즉, 그리디하게 문제를 풀 수 있다.

 

dp값은 간단한 트리 dp로 구할 수 있다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def rec(cur, p=-1):
    for nxt in adj[cur]:
        if nxt != p:
            rec(nxt, cur)
            if dp[cur] == 0: dp[cur] = dp[nxt] + 1
            else: dp[cur] = min(dp[cur], dp[nxt] + 1)

def dfs(cur, x, p=-1):
    global ans
    for nxt in adj[cur]:
        if nxt != p:
            if dp[nxt] <= x + 1: ans += 1
            else: dfs(nxt, x + 1, cur)

n, k = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)
dp = [0] * (n + 1)
rec(k)
ans = 0
dfs(k, 0)
print(ans)

굉장히 간단한 코드로 풀 수 있다.