[BJ] 17471 - 게리맨더링

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

오늘은 백준 17471번 문제 게리멘더링에 대해 알아보도록 하겠습니다.

 

회의 시간 : 2019.10.21 (토) 17:00 ~ 19:00

회의 장소 : 패스트파이브 서울숲점 2D

 

 

접근 방법

딱 봐도 두가지 개념이 혼합된 문제입니다. 연결 요소(connected component)와 조합(combination)입니다. 큰 요점은 모든 노드를 빠짐없이 두개의 그룹으로 분할하며, 동시에 두 그룹은 연결 요소여야 합니다. (물론 다른 방법으로도 풀 수 있을 거에요. 아마도..)

이 외에도 비트마스크, 서로소 집합 등등 여러가지 개념들을 이용한 분들도 계시더라구요.

어찌됬건, 제가 생각하는 키 포인트들은 다음과 같습니다.

• 연결 요소 : 각 지역구는 연결요소여야 합니다. 당연히 DFS, visited, 인접 행렬 및 인접 배열도 따라오겠죠?
• 조합 : 그래프를 두 지역구로 나누는 데 사용합니다.
• 분할 후 연결 요소인지 판단

사실 처음엔 연결 요소 여부 및 개수를 먼저 확인하고 나머지 로직을 수행하도록 구현했습니다. 좋은 방법인지는 모르겠지만, 나머지 로직을 어떻게 해야 할 지 막막해서 구글의 도움을 받았습니다.. ㅎㅎ

 

 

조합

문제의 특성상, 그래프의 모든 노드를 양분해야 합니다. 즉, 서로소 집합을 만들어야 한다는 뜻입니다.

조합을 이용하는 경우, 서로소 집합이라는 전제조건을 이용한다면 알고리즘 수행 횟수를 반으로 줄일 수 있습니다.

예를 들어, [1, 2, 3, 4, 5]로 주어진 집합에서 3개를 뽑는 조합을 생각해봅니다.

• $_{5}C_{1} : [1], [2], ..., [5]$
• $_{5}C_{2} : [1, 2], [1, 3], ..., [4, 5]$
• $_{5}C_{3} : [1, 2, 3], [1, 2, 4], ..., [3, 4, 5]$
• $_{5}C_{4} : [1, 2, 3, 4], [1, 2, 3, 5], ..., [2, 3, 4, ,5]$

$_{5}C_{1} : [1]$의 경우에 대해, 다른 집합은 [2, 3, 4, 5]가 됩니다. $_{5}C_{4} : [2, 3, 4, 5]$의 경우에 대해, 다른 집합은 [1]이 됩니다.

n이 5인 경우 r은 1, 2만 확인하면 되며, n이 6인 경우에 r은 1, 2, 3까지만 확인하면 됩니다.

간단하게 표현하면 $r : \lfloor{\frac{n}{2}}\rfloor$이 됩니다.

 

 

슈도 코드

위 개념들을 바탕으로 간단하게 로직을 구성하면 다음과 같습니다.

1. 조합을 이용하여, 그래프를 양분한다.
2. 양분한 두 집합에 대해, 단일 연결 요소 여부를 판단한다.
3. 두 집합 모두 단일 연결 요소라면 두 집합의 차이를 구한다.
4. 모든 조합에 대해 2~3을 반복하여, 최소값을 출력한다.

 

 

풀이 코드 (javascript)

 const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const input = [];
let N = 0;
let adjacencyList = [];

// 인접 배열을 만드는 함수
function makeAdjacencyList(input, graph) {
    const adjacencyList = input.splice(2);
    return adjacencyList.map((list, index) => {
        return {
            index,
            value: graph[index],
            number: list.splice(0, 1)[0],
            neighbors: list.map(adjacency => adjacency - 1)
        };
    });
}

// 인접 배열을 목적에 맞게 정렬하는 함수
// 각 행은 인접한 이웃의 수에 대해 내림차순으로 정렬하고
// 각 행의 neighbors는 이웃의 수에 대해 오름차순으로 정렬한다
function sortAdjacencyList(adjacencyList) {
    adjacencyList.sort((a, b) => b.number - a.number);
    adjacencyList.forEach(nodeObj => nodeObj.neighbors.sort((a, b) => adjacencyList[a].number - adjacencyList[b].number));
}

// 특정 집합이 하나의 연결요소인지 판단하는 함수
function isConnectedComponent(adjacencyList, specificSet) {
    const visited = new Array(specificSet.length).fill(false);
    let count = 0;

    specificSet.forEach(nodeValue => {
        const nodeIndex = adjacencyList.findIndex(nodeObj => nodeObj.value === nodeValue);
        if (dfs(nodeIndex, adjacencyList, visited)) count++;
    });

    return count === 1;
}

// 연결 요소를 판단하기 위한 DFS 함수
function dfs(index, adjacencyList, visited) {
    if (visited[index]) return;
    visited[index] = true;

    for (let i = 0; i < adjacencyList[index].number; i++) {
        dfs(adjacencyList[index].neighbors[i], adjacencyList, visited);
    }
    return true;
}

// 그래프를 조합을 이용해 양분하는 함수
function devide(graph, N, adjacencyList) {
    const maxR = Math.floor(N / 2);
    const combinationList = [];
    let minGap = Infinity;

    for(let r = 1; r <= maxR; r++) {
        combination(graph, [], combinationList, N, r, 0);
        
        for(let j = 0; j < combinationList.length; j++) {
            const firstSet = combinationList[j];
            // 조합의 모든 경우에 대해 secondSet을 구한다
            const secondSet = getSecondSet(graph, firstSet);
            // 두 집합에 대해 각각 연결요소의 개수가 1인지 확인한다
            if(!isConnectedComponent(adjacencyList, firstSet)) continue;
            if(!isConnectedComponent(adjacencyList, secondSet)) continue;
            // 맞다면 둘의 차이를 구한다.
            const gap = Math.abs(getSetSum(firstSet) - getSetSum(secondSet));
            minGap = gap < minGap ? gap : minGap;
        }
    }

    return minGap === Infinity ? -1 : minGap;
}

// 서로소 집합을 구하는 함수
function getSecondSet(graph, firstSet) {
    return firstSet.reduce((acc, val) => {
        const index = acc.findIndex(value => value === val);
        if(index > -1) acc.splice(index, 1);
        return acc;
    }, Object.assign([], graph));
}

// 조합을 수행하는 함수
function combination(source, target, final, n, r, count) {
    if (r === 0) final.push(target);
    else if (n === 0 || n < r) return;
    else {
        target.push(source[count]);
        combination(source, Object.assign([], target), final,n - 1, r - 1, count + 1);
        target.pop();
        combination(source, Object.assign([], target), final,n - 1, r, count + 1);
    }
}

// 집합의 합을 구하는 함수
function getSetSum(set) {
    return set.reduce((acc, val) => acc + val);
}

rl
    .on("line", function(line) {
        input.push(line.split(" ").map(token => Number(token)));
        if (input.length === 1) N = Number(input[0][0]);
        if (input.length >= N + 2) rl.close();
    })
    .on("close", function() {
        const graph = input[1];
        adjacencyList = makeAdjacencyList(input, graph);
        sortAdjacencyList(adjacencyList);
        console.log(devide(graph, N, adjacencyList));
        process.exit();
    });

예제는 맞지만 통과는 못하는 코드입니다..

 

 

참고

https://ratsgo.github.io/data%20structure&algorithm/2017/11/12/disjointset/

Disjoint Set · ratsgo's blog

https://gorakgarak.tistory.com/523

조합(Combination) 알고리즘