[Gold II] 우수 마을 - 1949
성능 요약
메모리: 47684 KB, 시간: 576 ms
분류
다이나믹 프로그래밍(dp), 트리에서의 다이나믹 프로그래밍(dp_tree), 트리(trees)
문제 설명
N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있을 때, 두 마을이 인접해 있다고 한다.
이 나라의 주민들에게 성취감을 높여 주기 위해, 다음 세 가지 조건을 만족하면서 N개의 마을 중 몇 개의 마을을 '우수 마을'로 선정하려고 한다.
- '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
- 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
- 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.
각 마을 주민 수와 마을 사이의 길에 대한 정보가 주어졌을 때, 주어진 조건을 만족하도록 '우수 마을'을 선정하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 이하이다. 셋째 줄부터 N-1개 줄에 걸쳐서 인접한 두 마을의 번호가 빈칸을 사이에 두고 주어진다.
출력
첫째 줄에 '우수 마을'의 주민 수의 총 합을 출력한다.
풀이
Tree 구조의 구현을 이해하지 못해 loosie님의 코드를 참고해 분석하며 작성해봤다.
우선 사용되는 변수는 각 마을 인구수를 기록할 int[] po, int[][]dp, tree구조의 연결관계를 위한 List<Integer>[] list가 있다.
dp에는 점화식에 따라 DFS로 최대값을 누적해서 더해나갈 것이기 때문에 아직 계산을 거치지 않은 마을을 구분하기 위해 초기값 -1을 채운다.
1 2 3 4 5 6 7 8 9 10 11 | for( int i = 0 ; i < n+1 ; i++ ) { Arrays.fill(dp[i], -1); // dp -1로 초기값 설정 } for( int i = 1; i < n+1 ; i++ ) { po[i] = sc.nextInt(); // 각 마을 별 인구수 배열 입력 } list = new ArrayList[n+1]; for( int i = 0; i < n+1; i++ ) { list[i] = new ArrayList<>(); // Tree구조 연결관계 list } | cs |
각 마을 간 Tree구조의 인접관계를 표현하기 위한 list의 요소를 add한다.
1 2 3 4 5 6 7 | for( int i = 0 ; i < n-1 ; i++ ) { int from = sc.nextInt(); int to = sc.nextInt(); list[from].add(to); list[to].add(from); // 연결관계 입력 } | cs |
select 라는 함수로 DFS 탐색을 통한 우수마을 선정을 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | private static int select(int now, int prev, int flag) { int len = list[now].size(); if( dp[now][flag] != -1 ) return dp[now][flag]; // 이미 select를 시행한 마을이면, 해당 dp값 리턴후 종료. dp[now][flag] = 0; // 현재 dp 초기화 for( int i = 0 ; i < len ; i++ ) { int next = list[now].get(i); // list로부터 다음 select 대상 선별 if( next != prev ) { // 되돌아가는 경우 제외 if( flag == 1 ) { // 이전 마을을 선정했다면, dp[now][flag] += select(next, now, 0); // 다음 select 시행 } else { // 이전 마을이 선정되지않았다면, dp[now][flag] += Math.max(select(next,now,1)+po[next], select(next,now,0)); // now 마을을 선정 , 다음마을부터 DFS하는 것 중 최대값. } } } return dp[now][flag]; } | cs |
dp, po, list는 static한 전역변수로 설정하고, 현재 탐색할 현재마을 번호,now, select함수를 통해 전달해온 이전 마을 번호, prev 이전 마을이 선정 됐는지 여부를 알리기 위한 int flag를 parameter로 사용한다.
선정 여부를 결정하는 것은, 우선 이전 마을이 선정됐는지 여부가 가장 중요하다. 이전 마을이 선정됐을 경우 now는 반드시 선정돼서는 안된다. 이전 마을이 선정되지 않았을 경우는 now가 선정됐을 경우와 now를 선정하지 않고 now를 prev로 하여 select를 한 후 두 결과를 비교하여 더 큰 값을 주는 것을 선택해야한다.
현재 마을의 dp값이 초기값인 -1인지 확인하여 한 마을이 중복하여 now로 지정됐는지를 확인하고, dp[now][flag]를 0으로 초기화한다. 다음 now가 될 next 마을의 번호를 list를 통해 선언한 후, 양방향이 아닌 단방향으로 이루어질 수 있도록, 되돌아가는 경우를 제외하고 앞서 말한 이전 마을이 선정됐는지 여부에 따라 if와 else로 나눈다.
reference : https://loosie.tistory.com/226
