[JavaScript] 백준 17471 게리맨더링 (JS)

게리맨더링

📚 문제 설명

1부터 N까지의 선거구가 있다.
각각의 선거구의 연결 관계와 인구수가 주어질 떄, 선거구를 2개로 나누려고 한다.
두 선거구의 인구수 차이가 최소가 될 때를 찾아라.

단, 각각의 선거구는 연결되어 있어야한다.
예를 들어 A - A - B - B 는 가능하지만, A - B - A - B 는 불가능하다.

👨🏻‍💻 풀이 과정

기본적인 과정은 다음과 같다.

1. 조합 진행.
2. BFS함수를 이용해 연결되어 있는지 확인.
3. 2번 조건을 통과하면 인구 계산.

// BFS를 이용해서 연결되어 있는지 확인.
const BFS = (now, total, team) => {

};

// A 구역의 갯수를 주면 그 갯수만큼의 조합을 만들어줌.
const Combination = (A, arr, last) => {
    if (arr.length === A) {
        // BFS를 이용해 연결되어 있는지 확인.
      	// 연결되어 있다면 인구수 계산.
        return;
    }

    // 재귀를 이용해 조합.
    for (let i = last; i < N; i++) {
        Combination(A, [...arr, i], i + 1);
    }
};

// 1개부터 N-1 개까지 조합 실행.
for (let i = 1; i < N; i++) {
    Combination(i, [0], 1);
}

// 불가능.
min = min === Number.MAX_SAFE_INTEGER ? -1 : min;
// 출력.
console.log(min);

💡Combiantion 함수 (조합)

• 재귀를 통해 조합.
• A개 만큼 조합을 했다면 종료.
  • teamA, teamB 갱신.
  • BFS() 함수로 연결 확인.
    • 인구 계산.

    // A 구역의 갯수를 주면 그 갯수만큼의 조합을 만들어줌.
    const Combination = (A, arr, last) => {
        if (arr.length === A) {
            teamA = arr;
            let tmp = [];
            // B팀 갱신.
            for (let i = 0; i < N; i++) {
                if (arr.includes(i)) continue;
                tmp.push(i);
            }
            teamB = tmp;
            // B팀 수
            const B = N - A;

            // 두 팀이 조건에 맞게 연결된다면.
            if (BFS(teamA[0], A, teamA) && BFS(teamB[0], B, teamB)) {
                let sumA = 0;
                let sumB = 0;
                // 인구 계산.
                POPULATION.forEach((value, index) => {
                    if (teamA.includes(index)) {
                        sumA += value;
                    } else {
                        sumB += value;
                    }
                });
                min = Math.min(min, Math.abs(sumB - sumA));
            }
            return;
        }

        // 재귀를 이용해 조합.
        for (let i = last; i < N; i++) {
            Combination(A, [...arr, i], i + 1);
        }
    };

💡 BFS 함수

다음 위치가 아직 가지 않은 위치이고, team 에 속한 위치라면 이동.

    // BFS를 이용해서 연결되어 있는지 확인.
    const BFS = (now, total, team) => {
        let queue = [now];

        let index = 0;
        let visited = Array.from({length: N}, _ => false);
        visited[now] = true;

        while (queue.length > index) {
            const NOW = queue[index];
            for (let i = 0; i < lines[NOW].length; i++) {
                const NEXT = lines[NOW][i];
                if (!visited[NEXT] && team.includes(NEXT)) {
                    queue.push(NEXT);
                    visited[NEXT] = true;

                }
            }
            index++;
        }
        return visited.filter(v => v === true).length === total;

    };

💡전체 코드

    let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
    let idx = 0;
    const N = parseInt(input[idx++]);
    const POPULATION = input[idx++].split(' ').map(Number);
    let lines = Array.from({length: 6}, _ => []);
    // A팀 B팀 나눠서 저장.
    let teamA = [];
    let teamB = [];
    let min = Number.MAX_SAFE_INTEGER;
    // 연결 관계 저장.
    for (let i = 0; i < N; i++) {
        lines[i] = input[idx++].split(" ").slice(1).map(Number).map(v => v - 1);
    }

    // BFS를 이용해서 연결되어 있는지 확인.
    const BFS = (now, total, team) => {
        let queue = [now];

        let index = 0;
        let visited = Array.from({length: N}, _ => false);
        visited[now] = true;

        while (queue.length > index) {
            const NOW = queue[index];
            for (let i = 0; i < lines[NOW].length; i++) {
                const NEXT = lines[NOW][i];
                if (!visited[NEXT] && team.includes(NEXT)) {
                    queue.push(NEXT);
                    visited[NEXT] = true;

                }
            }
            index++;
        }
        return visited.filter(v => v === true).length === total;

    };

    // A 구역의 갯수를 주면 그 갯수만큼의 조합을 만들어줌.
    const Combination = (A, arr, last) => {
        if (arr.length === A) {
            teamA = arr;
            let tmp = [];
            // B팀 갱신.
            for (let i = 0; i < N; i++) {
                if (arr.includes(i)) continue;
                tmp.push(i);
            }
            teamB = tmp;
            // B팀 수
            const B = N - A;

            // 두 팀이 조건에 맞게 연결된다면.
            if (BFS(teamA[0], A, teamA) && BFS(teamB[0], B, teamB)) {
                let sumA = 0;
                let sumB = 0;
                // 인구 계산.
                POPULATION.forEach((value, index) => {
                    if (teamA.includes(index)) {
                        sumA += value;
                    } else {
                        sumB += value;
                    }
                });
                min = Math.min(min, Math.abs(sumB - sumA));
            }
            return;
        }

        // 재귀를 이용해 조합.
        for (let i = last; i < N; i++) {
            Combination(A, [...arr, i], i + 1);
        }
    };
    for (let i = 1; i < N; i++) {
        Combination(i, [0], 1);
    }
    min = min === Number.MAX_SAFE_INTEGER ? -1 : min;
    console.log(min);

🧐 후기

솔직히 이렇게 풀어서 통과했지만 전체적으로 풀이가 굉장히 맘에 들지 않는다.
우선 인구 계산 부분은 BFS() 함수 내부로 옮길 수 있을 것 같고 A팀과 B팀을 나눌 때, 저 방법이 최선인지 고민이 된다.
비트 마스킹을 이용해서 2진법을 이용하면 팀을 더 쉽게 나눌 수 있지 않을까 생각하고 있으며, 이 방법이 더 효율적인지 현재 고민중이다.