[Java] 17471번 : 게리맨더링

https://www.acmicpc.net/problem/17471

17471번: 게리맨더링

 

지옥불맛 게리맨더링 진짜 다 패버려

 

결국 이겨줬다. 내가 패줬다

 

왜 이렇게 제출이많냐고? 처음 풀 때 도움을 너무 많이 받아서,,,

코드 정리를 싸악 하다보니까 필요없는 코드가 너무 많아가지고 정리하다보니 제출 수가 늘어났다,,,그리고 다시 풀다보니 그냥 게리맨더링 패버린 사람됐다.

 

[풀이방법]

나는 조합과 bfs 를 활용해서 풀었다. 

문제를 보면, 무조건 2팀으로 나누어야하고, 그 팀이 연결되어 있음을 확인해야 했기에 2가지 방식을 활용했다!

 

조합을 먼저 보면, gCnt는 그룹이 몇개나 지어졌는지에 대한 변수이다, 그리고 visited 배열을 이용해서 true, false에 따라 2팀으로 분리했다. 백준 문제 중에 링크와 스타트와 아주 유사하다! 

 

그리고 연결이 되어있는 지를 확인하기 위해 bfs를 활용했다. 같은 팀인지를 확인하기 위해 bfs에 visited의 값을 주어서 a 팀인지 b 팀인지를 확인했다...!

public static void combi (int start, int depth) {
    int gCnt=0;
    int aTeam=0, bTeam=0;
    Arrays.fill(check, false);
    // team 분리
    for(int i=0;i<n;i++) {
        if(visited[i]) aTeam+=arr[i];
        else bTeam+=arr[i];
    }
    // 연결 되어 있는 지 check
    for(int i=0;i<n;i++) {
        if(!check[i]) {
            bfs(i, visited[i]);
            gCnt++;
        }
    }
    if(gCnt==2) {
        ret = Math.min(ret, Math.abs(aTeam-bTeam));
    }

    for(int i=start;i<n;i++) {
        if(!visited[i]) {
            visited[i] = true;
            combi(i, depth+1);
            visited[i] = false;
        }
    }
}

 

bfs 함수를 확인했을 때, 같은 팀이면서 이어져있는걸 확인하기 위해 해당 노드에 값이 전달받은 team의 값과 같은지를 비교했다.

같은 팀 일때만 큐에 넣어줘야 하므로!!

public static void bfs(int u, boolean team) {
    q = new LinkedList<>();
    q.add(u);
    check[u] = true;

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

        for(int i=0;i<list[x].size();i++) {
            int next = list[x].get(i);
            if(!check[next] && visited[next]==team) {
                q.add(next);
                check[next]=true;
            }
        }
    }
}

 

결과를 저장하는 변수는 ret 으로 지정해서 combi 함수를 보면, 그룹이 2개로 잘 나누어졌을 때 해당 그룹에 대한 인원수의 차이값을 저장했다. 그리고 ret 에 값이 부여되지 않았을 때는 나눌 수 없다는 의미 이므로 -1을 저장했다.

combi(0,0);

if(ret==Integer.MAX_VALUE) {
    ret = -1;
}

System.out.println(ret);

 

아래는 내가 직접 그려본 그림이다,,,한문제 푸는데 이게 맞는지 모르겠지만, 나는 아주 스튜핏하다,,,ㅠㅡㅠ

 

 

허허,,,,엉망진창이지만,,,이해하면 됐지 뭐~!~!~~~~!

 

쨋든 전체 코드는 아래 

[전체코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n, ret=Integer.MAX_VALUE;
    static int arr[];
    static List<Integer> list[];
    static boolean visited[], check[];
    static Queue<Integer> q;

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

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        arr = new int[n];
        list = new ArrayList[n];
        visited = new boolean[n];
        check = new boolean[n];

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            list[i] = new ArrayList<>();
        }

        int cnt=0;
        for(int i=0;i<n;i++) {
            st = new StringTokenizer(br.readLine());
            cnt = Integer.parseInt(st.nextToken());
            for(int j=0;j<cnt;j++) {
                int tmp = Integer.parseInt(st.nextToken());
                list[i].add(tmp-1);
            }
        }

        combi(0,0);

        if(ret==Integer.MAX_VALUE) {
            ret = -1;
        }

        System.out.println(ret);

    }

    public static void combi (int start, int depth) {
        int gCnt=0;
        int aTeam=0, bTeam=0;
        Arrays.fill(check, false);
        // team 분리
        for(int i=0;i<n;i++) {
            if(visited[i]) aTeam+=arr[i];
            else bTeam+=arr[i];
        }
        // 연결 되어 있는 지 check
        for(int i=0;i<n;i++) {
            if(!check[i]) {
                bfs(i, visited[i]);
                gCnt++;
            }
        }
        if(gCnt==2) {
            ret = Math.min(ret, Math.abs(aTeam-bTeam));
        }

        for(int i=start;i<n;i++) {
            if(!visited[i]) {
                visited[i] = true;
                combi(i, depth+1);
                visited[i] = false;
            }
        }
    }

    public static void bfs(int u, boolean team) {
        q = new LinkedList<>();
        q.add(u);
        check[u] = true;

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

            for(int i=0;i<list[x].size();i++) {
                int next = list[x].get(i);
                if(!check[next] && visited[next]==team) {
                    q.add(next);
                    check[next]=true;
                }
            }
        }
    }

}