BOJ 15686) 치킨 배달 -> 조합(Combination) 정리

 골드 5인데도 하루를 꼬박 썼다. 직전에 유사한 문제 (BOJ 14502 연구소 - https://www.acmicpc.net/problem/14502)를 풀어서 조합을 이용한 풀이를 빨리 떠올렸고, 하다못해 구글링해서 아주 유사한 코드를 발견했음에도 어디가 문제인지 몰라서 한참을 헤맨 문제. (난 알고리즘 팔생각도 없고 코테합만 안정적으로 할 딱 그정도 수준만 되고싶을 뿐인데 참 어렵다.)

 

 

 

문제 정리

 간단하게 정리하면, "NxN 크기의 도시에 집들과 치킨집들이 있다. 이 치킨집들의 숫자를 M개까지 줄일 때, '치킨 거리'의 합의 최소값을 구하시오. (치킨 거리란, 임의의 집에서 치킨집까지 거리의 최소값을 의미한다.)"로 정리할 수 있다.

 

 

풀이

 처음에는 NxN의 인접 행렬로 도시를 표현하고 나서, 처음 존재하는 치킨집을 k개라고 하면 폐업할 치킨집을 구하는 조합(kC(k-M))을 이용해서 폐업 치킨집을 선택하고, 선택된 조합마다 bfs를 사용해서 집-치킨집 거리를 구한 후 최소값을 선택해주면 된다고 생각했다. 하지만 계속 시간초과가 떠서 고쳤던 목록을 나열하겠다.

 

1. LinkedList -> ArrayList

> LinkedList는 연결 리스트 기반, ArrayList는 배열 기반의 리스트이므로, .get()을 통해서 조회하는데는 인덱스를 바로 활용할 수 있는 ArrayList가 유리하다. 반면 LinkedList는 .remove()를 통해 삭제하는데 좋은 효율을 가진다.

(참고: https://eckrin.tistory.com/136)

 

2. 인접 행렬과 인접 리스트

> 인접 행렬의 경우 구현이 쉽다는 장점을 가지지만, 해당 알고리즘에서는 집과 치킨집 사이의 거리를 구하기 위해서 좌표만 필요로 하므로(map[i][j]가 0인 지점의 정보를 필요로 하지 않는다), 각각 집과 치킨집의 정보를 저장하는 인접 리스트로 저장하면 필요한 정보만 리스트로 저장할 수 있다.

추가로 인접 행렬을 이용한다면 bfs를 사용한 탐색이 자연스럽게 떠오르게 되는데, 인접 리스트로 각각의 정보를 저장해놨다면 bfs를 사용할 필요 없이 O(집개수*치킨집개수)의 고정된 시간복잡도로 최단거리(치킨 거리)를 탐색 가능하다.

 

3. dfs를 이용한 조합(Combination)

> 문제를 푸는데 결정적인 부분이었다. 14502 연구소 문제에서 활용한 조합은 다음과 같다.

public static void makeWall(int depth) {
    if(depth==3) {
        rst = Math.max(rst, safe_num - bfs() - 3);
        return;
    }

    //NxMC3
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            if(map[i][j]==0) {
                map[i][j] = 1;
                makeWall(depth+1);
                map[i][j] = 0;
            }
        }
    }
}

NxM크기의 map에서, map[i][j]가 0인 부분 중에서 3개를 골라 1로 바꾸어주는 방식의 백트래킹을 이용한 조합이다.

여기서는 3<=N,M<=8로 N과 M이 매우 적었고, 정확히 3개만을 고르는 로직이므로 별다른 처리 없이 NxM 모두를 순회하면서 백트래킹을 진행하였다. 이 경우 최대 O((8*8)^3)=O(26만)정도의 시간복잡도를 가지기 때문이다.

 

 하지만 이번 문제는 최대 50x50 크기의 map을 대상으로 하고, 최대 12개의 치킨집을 고르게 될 수도 있으므로 시간복잡도가 매우 증가해 최대 O((50*50)^12)=O(59,604,644,775,390,625,000,000,000,000)의 시간복잡도를 갖게 될 수도 있다.

조금 더 효율적인 방법을 사용하여, 처음 존재하는 치킨집에서 닫을 치킨집을 구하는 방식으로 식을 세운다고 가정해도, 문제 조건에 따라 치킨집이 최대 13개 존재할 수 있으므로 주어지는 M값에 따라서 O(13^6)=O(480만)정도가 필요해지게 된다. 이러면 각 케이스마다 최단 치킨거리를 구하기 위한 로직(O(집개수*치킨집개수)=O(2487*13)=O(32331))을 돌려야 하므로 최종적으로 O(155,188,800,000)내외의 시간복잡도를 가지게 된다.

private static void combination(int depth, int start) {
    if(depth==(totalM-M)) {
        totalDistance = Math.min(getChickenDistance(), totalDistance);
        return;
    }

    for(int i=0; i<chickenList.size(); i++) {
        if(!isClosed[i]) {
            isClosed[i] = true;
            combination(depth+1, start+1);
            isClosed[i] = false;
        }
    }
}

 

따라서 이러한 경우는 다음과 같이 풀 수 있다.

private static void combination(int depth, int start) {
    if(depth==(totalM-M)) {
        totalDistance = Math.min(getChickenDistance(), totalDistance);
        return;
    }

    for(int i=start; i<chickenList.size(); i++) { //start부터 탐색
        if(!isClosed[i]) {
            isClosed[i] = true;
            combination(depth+1, i+1); //호출시 i+1부터 재귀
            isClosed[i] = false;
        }
    }
}

"조합은 순서가 중요하지 않으므로, 순서를 정해놓고 뽑아주면 된다."

 

start라는 정수가 매개변수에 추가되었는데, 이 변수는 재귀호출이 이루어질때마다 지금까지 고려하여 탐색한 부분을 다시 탐색하지 않도록 한다. 참고로 조합은 시간복잡도가 O(2^n)으로 매우 크다.