백준 17471번(Java)

문제는 아래와 같다.

예제 입력과 답은 아래와 같다.

6
5 2 3 4 1 2
2 2 4
4 1 3 6 5
2 4 2
2 1 3
1 2
1 2

1

자세한 건 직접 가서 보자.
https://www.acmicpc.net/problem/17471

---

문제가 참 재밌어 보인다. 시간 많이 걸릴 거 같다는 뜻이다.
어쨌든 풀어봐야 하니, 어떻게 풀어볼지 생각해보자.
눈에 띄는것부터 찾아보자.

1. 구역을 나누어봐야한다. Union-Find가 생각났으나, 필자는 Union-Find와 아직 어색한 사이다. 그러니까 가장 친한 BFS로 풀어보자.
2. 그룹을 만들어줘야한다. 어떻게 만드냐? 완전탐색으로 싹 찾아봐야한다.
3. 그룹을 만들고 구역이 2개이며, 각각이 조건이 성립한 구역임이 확인되면 각 그룹의 인원 차이를 계산해서 기존의 수와 비교하여 가장 적은 수를 저장하자.

보기만해도 복잡해보여서 하기 싫으나 어쩌겠나, 풀어야지.

사실 그렇게 복잡하지 않다. 하나씩 해보자.

첫번째,
그룹을 만들어 보자.
그룹은 1개부터 n/2까지 만드는 것이 좋다.
n-1개 까지 만드는 것과 1개만 만드는 것이 똑같은 일 두번 하는것과 같다.
일 두번 하는게 가장 기빨리는 일이니 가차없이 버리자.

두번째,
그룹이 조건에 성립한 그룹인지 확인한다.
그룹은 서로 이어져 있어야 하며, 떨어져 있으면 안된다.
서로 떨어져 있는것은 BFS를 두번 사용해서 확인할 수 있다.

세번째,
조건이 성립한 그룹의 인원수 차이를 계산한다.
기존의 값과 새로 계산한 값을 비교한 후 가장 작은 값을 저장한다.

위의 과정으로 우리는 정답을 찾을 수 있다. 신난다!

그러면 한번 코드를 작성해보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int[] person;
    static LinkedList<Integer>[] route;
    static boolean[] visited;
    static int ans = Integer.MAX_VALUE;

    static boolean checkRoute(int cnt){
    	//그룹 별 시작지점을 찾아보자.
        int s1 = 0;
        int s2 = 0;
		
        //Group1
        for(int i = 1; i <= n; i++){
            if(visited[i]){
                s1 = i;
                break;
            }
        }
        //Group2
        for(int i = 1; i <= n; i++){
            if(!visited[i]){
                s2 = i;
                break;
            }
        }
		
        //BFS로 Group1이 이어져 있는지 찾아보자
        Queue<Integer> q = new LinkedList<>();
        //새로운 방문체크 배열을 만들어주자.
        boolean[] check = new boolean[n + 1];
        q.add(s1);
        check[s1] = true;
        int groupCnt1 = 1;

        while(!q.isEmpty()){
            int cur = q.poll();

            for(int nxt : route[cur]){
            	//Group1의 조건인 visited가 true이어야하며,
                //방문하지 않는 노드를 찾아간다.
                if(visited[nxt] && !check[nxt]){
                    check[nxt] = true;
                    q.add(nxt);
                    groupCnt1++;
                }
            }
        }
		
        // visited의 true의 개수, 즉 Group1의 개수가
        // 지정한 그룹의 크기와 다르다면 이어져 있지 않는것이다.
        // 그러므로 도자기 장인의 정신으로 가차없이 버리자.
        if(groupCnt1 != cnt)
            return false;


		// 이번에는 Group2의 개수를 찾아볼것이다.
        q.clear();
        q.add(s2);
        check = new boolean[n + 1];
        check[s2] = true;
        int groupCnt2 = 1;
        while(!q.isEmpty()){
            int cur = q.poll();

            for(int nxt : route[cur]){
            	// Group2의 조건인 visited가 false인 것만 찾고
                // 방문하지 않은 노드를 찾아가자.
                if(!visited[nxt] && !check[nxt]){
                    check[nxt] = true;
                    q.add(nxt);
                    groupCnt2++;
                }
            }
        }
		
        // Group2의 크기가 전체의 크기인 n에서 Group1의 크기이자
        // 설정했던 크기인 cnt를 뺀 n - cnt와 같지 않으면
        //이어져있지 않는것이다.
        if(groupCnt2 != n - cnt)
            return false;
		
        //위의 조건을 통과했다면 이 그룹은 옳바른 그룹이므로 통과시키자.
        return true;
    }
    
    //사람의 수를 계산해보자
    static void checkPerson(int cnt){
        int area1 = 0;
        int area2 = 0;
		
        // 사람의 수를 계산하기에 앞서 각 그룹의 경로가 이어져있는지 확인한다.
        if(!checkRoute(cnt)) return;
		
        //경로가 확인되면 visited 배열로 구분하여 그룹의 인원수를 더한다.
        for(int i = 1; i <= n; i++){
            if(visited[i]) area1 += person[i];
            else area2 += person[i];
        }
		
        //절대값으로 저장해서 양을 측정하자.
        int diff = Math.abs(area1 - area2);
        //기존의 값과 비교하여 가장 작은것을 저장.
        ans = Math.min(ans, diff);
    }

	//완전탐색을 하는 과정이다.
    static void func(int start, int depth, int cnt) {
    	/*
        depth를 기준으로 그룹의 크기가 설정한 크기와 같다면
        인원수 차이를 계산하러 갈것이다. 
        */
        if (depth == cnt) {
            checkPerson(cnt);
            return;
        }
		
        for (int i = start; i <= n; i++) {
            visited[i] = true;
            func(i + 1, depth + 1, cnt);
            visited[i] = false;
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
		
        // 인원수 저장
        person = new int[n + 1];
        // 방문한 노드의 중복방문을 방지 겸 그룹을 true, false로 나누기 위해 사용한다.
        visited = new boolean[n + 1];

        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++){
            person[i] = Integer.parseInt(st.nextToken());
        }

        route = new LinkedList[n + 1];
        for(int i = 1; i <= n; i++)
            route[i] = new LinkedList<>();

        for(int i = 1; i <= n; i++){
            st = new StringTokenizer(br.readLine());

            int m = Integer.parseInt(st.nextToken());
            for(int j = 0; j < m; j++){
                route[i].add(Integer.parseInt(st.nextToken()));
            }
        }
        
        // 위의 부분은 입력을 받는 과정이다.
		
        for(int i = 1; i <= n/2; i++){
        	// 1부터 n/2까지 그룹의 크기를 제한하고 완전탐색 해보자.
        	func(1, 0, i);
        }
		
         /*
          ans는 정답이다. 정수의 가장 큰 크기로 초기화를 하였다.
          만약 ans가 초기화 된 그대로라면 두 선거구로 나눌 수 없는 경우이므로
         -1을 출력할 것이다.
        */
        if(ans == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(ans);
    }
}

필자의 코드는 static변수를 보고 아래부터 위로 읽으면 좋다.
필자도 위에서 아래로 코드를 보니, 이게 내 코드가 맞나 싶을 정도로 눈에 안들어와서 남긴다.

코드의 실행순서는 다음과 같다.

1. 입력을 받자
2. 그룹의 크기를 설정해주고 완전탐색(func) 실행
3. 설정한 그룹의 크기가 되었다면 인원수의 차이(checkPerson)를 계산하자.
4. 본격적으로 계산하기 전에 이게 조건에 성립하는 그룹인지 확인하자.(checkRoute)
5. 조건이 성립한 그룹이라면 이제 인원수의 차이를 계산하고 기존의 값과 비교하여 가장 작은 수를 저장하면 된다.
6. 최종 결과를 저장하는 변수인 ans가 초기화 했던 정수의 가장 큰 값(Integer.MAX_VALUE)라면 두 그룹으로 나눌 수 없는 것이니 -1을 출력하자. 아니라면 ans를 출력하면 된다.

그러면 짜잔!
정답이 된다!

이 문제는 보기에 쉽게 풀 수 있는 줄 알았다.
하지만 언제 어떤 조건으로 그룹을 만들고 이 그룹이 어떻게 적합한 그룹인지 확인하는지에 대한 것을 정리하고자 하는 것이 쉽지 않았다.
사실 그게 문제의 전부라 어려웠던 건가?
그럼에도 풀었다는 것에 의의를 둔다.

끝!