백준 2533번

접근 방식(알고리즘 분류)

• DFS + DP

내 풀이

import sys
#재귀할때 이거 안해주면 가끔 런타임나옴
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
Tree = [[] for _ in range(N+1)]
visited = [True for _ in range(N+1)]

for _ in range(N-1):
    u, v = map(int, input().split())
    Tree[u].append(v)
    Tree[v].append(u)

#[1,0]으로 초기화 해주는 이유는 현재 dp에 저장할 값은 얼리 어답터가 아닌 노드의 수를 구하는 것이기 때문이다.
DP = [[1,0] for _ in range(N+1)]

def DFS(cur):
    visited[cur] = False
    for i in Tree[cur]:
        if visited[i]:
            DFS(i)

            #해당 노드가 첫번째 인자엔 얼리 어답터가 아닐때 얼리어답터가 아닌 노드의 수
            DP[cur][0] += DP[i][1]
            #해당 노드가 두번째 인자엔 얼리 어답터일 때 얼리어답터가 아닌 노드의 수
            DP[cur][1] += max(DP[i][0], DP[i][1])

DFS(1)
#시작을 1번째 노드에서 했으므로 1번째 노드의 dp값으로 검사를 한다. --> 첫번째 인자가 재귀를 타고 마지막까지 도착해야하기 때문
print(N - max(DP[1][0], DP[1][1]))

느낀점

• 초기에 문제를 읽고 접근할때 트리구조로 접근하려 했기 때문에 시간을 오래 낭비했다.
  • 해당 문제는 상하 관계가 아니고 양방향이기에 트리 구조가 아니라 양방향 그래프 구조로 문제를 접근해야 한다.
• 시작점이 주어질때 가장 멀리있는 지점까지 도달한 다음 위로 타고올라와야 하기 때문에 BFS보단 DFS가 적합하다고 판단했다.
• 단순 배열에서 dp를 적용하는 것 보다 확실히 초기에 생각할 것이 많다는 것을 느꼈다. (특히 초기화)