Baekjoon[17471] - 게리맨더링

링크

17471번: 게리맨더링

문제설명

• 집합 check

문제풀이

• DFS로 풀었음

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main17471 {
    public static int Temp=0;
    public static int Ans=Integer.MAX_VALUE;
    public static int N;
    public static int[] people;
    public static int[] color;
    public static boolean[] visit;
    public static int[][] area;
    public static void BFS(int n, int area_color) {
        LinkedList<Integer> q = new LinkedList<>();
        visit[n]=true;    //visit함
        Temp+=people[n];
        q.add(n);
        int now;
        while(!q.isEmpty()) {
            now = q.poll();
            for (int i = 1; i <= area[now][0]; i++) {
                if(!visit[area[now][i]] && color[area[now][i]]==area_color) {
                    visit[area[now][i]]=true;
                    Temp+=people[area[now][i]];
                    q.add(area[now][i]);
                }
            }
        }
    }
    public static void Search(int cnt) {;
        if(cnt==N+1) {
            int valid=0;
//            2^N경우의 수를 다 만들었으면,
//            System.out.println(Arrays.toString(color));
            visit = new boolean[N+1];
            for (int i = 1; i <= N; i++) {
//                1번색상 마을 BFS체크하고, 값 저장.
                if(color[i]==1) {
                    BFS(i,1);
                    valid++;
                    break;
                }
            }
            int People0 = Temp;
            Temp=0;
            for (int i = 1; i <= N; i++) {
//                2번색상 마을 BFS체크하고, 값 저장.
                if(color[i]==2) {
                    BFS(i,2);
                    valid++;
                    break;
                }
            }
            int People1 = Temp;
            Temp=0;
//            모든 마을이 visit되었는지 확인(그래야 유효하게 2개로 나뉜 것임)
//            모든 마을이 visit되지 않아서 유효하지 않음
//            System.out.println(Arrays.toString(visit));
            for (int i = 1; i <= N; i++) {
                if(valid<2 || !visit[i]) {
                    Ans=Math.max(Ans, -1);
//                    System.out.println("UNVALID");
//                    System.out.println("break"+i+" "+Ans+" "+People0+" "+People1);
                    return;
                }
            }
//            모든 마을이 visit되어서 유효함
//            System.out.println("VALID");
            Ans = Math.min(Ans,Math.abs(People0-People1));
//            System.out.println(Ans+" "+People0+" "+People1);
            return;
        }
        for (int i = 1; i <= 2; i++) {
            color[cnt]=i;
            Search(cnt+1);
        }
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/baekjoon/17471.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        people = new int[N+1];
        color = new int[N+1];
        area = new int[N+1][N+1];

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

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            area[i][0] = Integer.parseInt(st.nextToken());
            for (int j = 1; j <=area[i][0]  ; j++) {
                area[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        Search(1);    //2^N의 경우의 수를 만든다
        if(Ans==Integer.MAX_VALUE)Ans=-1;
        System.out.println(Ans);
//        초기화
        Ans=Integer.MAX_VALUE;

    }
}

아쉬운점

• Ans=-1 처리를 마지막에 해줌. 중간의 -1은 무시해도됨.
  • 그냥 Max.Integer이 변하지 않았으면, 탈출을 못한다는 뜻.
• 경로 탐색할 때, 인덱싱 실수했음
  • area[now][i]가 기준인데 i로 기준을 잡아서 제대로 안돌아갔음.

잘한점

• O(N) = 2^10*DFS
  • 0.5초 제한이지만 이렇게 해도 될 것 같았음

다른풀이

• 인접 행렬을 Matrix 행렬로 변환시켰음.
• DFS로 방문체크가능함
• subset이라 (2^10)/2만큼의 경우의 수임.
• 인접행렬로 연결되어있으면 Union한 후 root 체크하면 됨