tree dp1 [Algorithm] 백준. 1949 우수마을 www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 트리 & 다이나믹 프로그래밍 껄끄러운 두 가지 방식이 합쳐진 문제. 양방향 그래프이므로, DFS방식으로 탐색하면서 visit 체크를 해서 이후에 되돌아 오는 일이 없도록 했다. 리프노드까지 도착한 후에 올라오면서 선택 시 최대 인원, 비선택 시 최대 인원을 저장하는 방식으로 구현하였다. 조건을 만족하려면, 현재 마을인원을 추가하는 경우엔 이웃한 마을의 인원은 추가되면 안되기 때문에, 이웃한 마을들의 비.. 2021. 4. 23. 이전 1 다음 728x90
