[백준 / BOJ] 1949 우수 마을 (Java)

문제

출처 : https://www.acmicpc.net/problem/1949

1949번: 우수 마을

N개의 마을로 이루어진 나라가 있다.

나라는 1부터 N까지의 번호로 표시되며, 트리구조 , 양방향 간선 으로 이루어져있다.

각 마을에는 C명의 주민이 살고있다. (C<=10000)

이때, 각 마을중 우수마을을 선정하려고 한다.

우수마을의 조건은 아래와 같다 

1. 우수 마을로 선정된 마을 주민 수의 총 합을 최대로 해야한다.

2. 우수 마을과 인접한 마을은 우수마을이 될수없다.

3. 우수마을로 선정되지못한 마을은 우수마을과 인접해있어야한다.

 

---

풀이

모든 경우를 봐줄경우 최대 2^10000이 걸리므로 다이나믹 프로그래밍으로 풀어야 했던 문제다.

 

아이디어는 다음과 같다.

1. 마을이 트리구조이므로, 마을을 더 작게 나눠도 트리구조이다.

2. 더 작게 나뉜 트리구조에서 최댓값을 구한다.

3. 2번에서 구한값을 토대로 더 큰 트리구조에서 최댓값을 구한다.

*이때, 모든 마을을 방문하기위해, 방문순서가 제일 늦은 마을부터(트리의 끝 마을) 방문해줘야한다.*

 

dp식을 세우기위한 조건을 생각해보자.

1. 현재 마을이 우수 마을이 될경우, 현재 마을의 자식마을은 전부 우수 마을이 아니여야한다.

2. 현재 마을이 우수 마을이 아닐경우, 현재 마을의 자식마을이 우수 마을이여도 되고 아니여도 상관없다.

 

위 조건을 토대로 dp식을 세워보자.

dp[우수마을인 경우 2 아닌경우 1][마을의 넘버] = 현재마을을 선택하기까지 최댓값

 

1. 현재 마을이 우수마을일 경우

for(int i = 0 ... ) dp[2][현재마을의 넘버] = dp[1][자식마을들]

 

2. 현재 마을이 우수마을이 아닌경우

for(int i = 0 ... ) dp[1][현재마을의 넘버] = max(dp[1][자식마을들], dp[2][자식마을들])

 

위 와같이 나온다.

 

구현한 소스코드는 아래와 같다.

 

    private int getDp(){
        int lastIdx = 1;
        while(!visitOrder.isEmpty()){
            int nowIdx = visitOrder.peek().num;
            visitOrder.poll();
            lastIdx = nowIdx; // 마지막 방문 마을 저장 1번마을부터 시작했으니 항상 1이긴할듯?
            // 자식노드들이 선택되지 않은경우 와 선택된 경우를 구해줌 
            dp[2][nowIdx] = citizen[nowIdx]; // 자식들이 선택되지않는다면 자신은 선택할수있으므로 2에 저장할것임.
            dp[1][nowIdx] = 0; // 마찬가지로 자식들이 선택되었다면 자신은 선택할수없으므로 0 으로 초기화
            for(int i = 0; i < node.get(nowIdx).size(); i++){
                int sonIdx = node.get(nowIdx).get(i);
                if(dp[1][sonIdx] != -1) dp[2][nowIdx] += dp[1][sonIdx]; // dp값이 -1인 경우, 초기화가 안되어있기때문에 자신의 부모노드임
                if(dp[2][sonIdx] != -1) dp[1][nowIdx] += Math.max(dp[1][sonIdx],dp[2][sonIdx]); // 선택 되지않은경우, 이전값이 선택된지 선택되지않았는지 알필요없음
            }
            
        }
        return Math.max(dp[1][lastIdx],dp[2][lastIdx]);
    }

visitOrder는 PriorityQueue로 자식들의 방문순서가 역순으로 저장되어있다.

 

 

---

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1949%20%EC%9A%B0%EC%88%98%EB%A7%88%EC%9D%84/Main.java

devxb/JJUNalgo