백준 15686번 - 치킨 배달

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

풀이

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

위의 예제를 보자.

• 집의 개수 : 6개
• 치킨집(가게)의 개수 : 2개

각각의 집은 치킨거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합니다.

각 집에서 모든 치킨집까지의 최단 거리를 각각 구할 수 있다. 이 중 가장 가까운 곳에 있는 치킨집까지의 거리가 해당 집의 치킨거리가 되는 것이다.

위의 예제에서 (0,1)의 집에서부터 한 번의 BFS(DFS도 가능)을 수행하면 모든 치킨집까지의 최단 거리를 구할 수 있다. 이런 식으로 각 집의 위치를 시작점으로 BFS를 수행(집의 개수만큼 BFS수행)하게되면, 모든 집에서부터 모든 치킨집까지의 최단거리를 구할 수 있게된다.

구한 값은 4차원 배열을 이용해 저장할 수 있다.

int[][][][] distList = new int[집의y좌표][집의x좌표][치킨집의y좌표][치킨집의x좌표]

예를 들어, dist[1][0][0][1]은 (1,0) 집에서 (0,1) 치킨집까지의 최단거리가 되는 것이다.

 

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다.

어떻게 고르면,도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

도시의 치킨거리 = 모든 집의 치킨 거리의 합이다.

치킨 집을 최대 M개 고를 수 있다고 했는데, 최대로 고를 수 있는 만큼 고르면 된다. 만약 M-X개를 골랐을 경우 도시의 치킨거리가 최소값이 된다면, M개를 골라도 동일하게 치킨거리는 최소값이 될 것이다. (치킨집이 많아진다고고 해도 각 집의 치킨 거리는 늘어나지 않는다.)

그러므로, K개의 치킨집 중 M개를 고르는 모든 경우를 만든 뒤(조합)에 도시의 치킨거리값이 최소가 되는 경우를 찾으면 된다.

 

정리

1. 모든 집에서부터 모든 치킨집까지의 최단거리를 미리 구해놓는다.
   • 각 집마다 BFS 이용하여 최단거리 탐색
   • 각 집을 찾기 위해 2차원 배열을 탐색하는 것은 불필요한 시간낭비이기 때문에, 미리 입력 받을 때 배열 값이 '1'인 경우, 집이므로 ArrayList를 이용하여 미리 집 List를 만들어 놓는다. (치킨집도 동일하게 미리 List 만들어놓기)
2. K개의 치킨집 중 M개를 고르는 모든 경우의 수를 조합한다.
   • 치킨집도 미리 입력받을 때 List로 만들어놓았기 때문에, 해당 List의 길이가 총 치킨집의 수가 된다.
3. 조합된 모든 경우에 대해 각각 도시의 치킨거리값을 구하고, 최소 값을 찾는다.

 

시간복잡도

집의 개수 = A
치킨집의 개수 = B
2차원 배열의 크기 = C

1. BFS의 시간복잡도는 O(C)이다. 그렇다면 1번의 모든 집에서부터 모든 치킨집까지의 최단거리를 미리 구하는 것은 O(AC) 의 시간복잡도를 가진다.
2. B개의 치킨집 중 M개를 고르는 조합은 O(2^B) 의 시간복잡도로 나타낼 수 있다.
3. 조합 후 각각의 도시의 치킨거리 값을 구하는 로직의 시간복잡도는 O(AB) 이다.

전체 시간복잡도는 O(AC + AB*2^B)

최악의 경우 = 100 * 2500 + 100 * 13 * (2^13) = 10,899,600 의 크기가 나온다고 보면, 대략 0.1초 걸린다고 볼 수 있다. (1억 = 1초)

 

시간복잡도 계산에 대한 부분은 오류가 있을 수 있습니다.. 피드백 부탁드립니다.

실제 시간은 0.3초 정도...

 

소스코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static String str;
    static StringTokenizer st;
    static int n;
    static int m;
    static int[][] arr;
    public static class Node{
        int isHome;
        int y;
        int x;
        int dist;
        public Node(int isHome, int y, int x, int dist) {
            this.isHome = isHome;
            this.y = y;
            this.x = x;
            this.dist = dist;
        }
    }
    static ArrayList<Node> homeList;
    static ArrayList<Node> marketList;
    static int[][][][] distList;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        homeList = new ArrayList<>();
        marketList = new ArrayList<>();
        str = br.readLine();
        st = new StringTokenizer(str);
        n = Integer.parseInt(st.nextToken());
        m= Integer.parseInt(st.nextToken());
        arr=new int[n][n];
        distList=new int[n][n][n][n];

        for(int i=0;i<n;i++){
            str=br.readLine();
            st=new StringTokenizer(str);
            for(int j=0;j<n;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j]==1){
                    homeList.add(new Node(1,i,j,0));
                }else if(arr[i][j]==2){
                    marketList.add(new Node(2,i,j,0));
                }
            }
        }

        int homeListSize = homeList.size();
        for(int i=0;i<homeListSize;i++){
            Node home = homeList.get(i);
            bfs(home);
        }

        int marketListSize = marketList.size();
        boolean[] chkMarket = new boolean[marketListSize];
        int result = selectMarket(chkMarket, 0, 0,marketListSize);
        System.out.println(result);
    }
    public static int cal(boolean[] chk){
        int sum = 0;
        int homeListSize = homeList.size();
        int marketListSize = marketList.size();

        for(int i=0;i<homeListSize;i++){
            int min = Integer.MAX_VALUE;
            Node home = homeList.get(i);
            for(int j=0;j<marketListSize;j++){
                Node market = marketList.get(j);
                if(chk[j]){
                    min = StrictMath.min(min, distList[home.y][home.x][market.y][market.x]);
                }
            }
            sum += min;
        }

        return sum;
    }
    public static int selectMarket(boolean[] chk, int idx, int cnt, int maxSize){
        if(cnt == m){
            return cal(chk);
        }
        if(idx >= maxSize){
            return Integer.MAX_VALUE;
        }

        int result = Integer.MAX_VALUE;

        int tmp = selectMarket(chk, idx+1, cnt, maxSize);
        result = StrictMath.min(result, tmp);

        chk[idx] = true;
        tmp = selectMarket(chk, idx+1, cnt+1, maxSize);
        result = StrictMath.min(result, tmp);
        chk[idx] = false;

        return result;
    }
    public static void bfs(Node start){
        int[] dy={-1,0,1,0};
        int[] dx={0,1,0,-1};
        Queue<Node> q = new LinkedList<>();
        boolean[][] chk = new boolean[n][n];

        chk[start.y][start.x] = true;
        q.add(start);

        while(!q.isEmpty()){
            Node node = q.remove();

            if(node.isHome==2){
                distList[start.y][start.x][node.y][node.x] = node.dist;
            }

            for(int d=0;d<4;d++){
                int ty=node.y+dy[d];
                int tx=node.x+dx[d];
                if(ty<0 || ty>=n || tx<0 || tx>=n){
                    continue;
                }
                if(chk[ty][tx]){
                    continue;
                }
                chk[ty][tx] = true;
                q.add(new Node(arr[ty][tx],ty,tx,node.dist+1));
            }
        }

    }
}