[BOJ 15684] 치킨 배달 - JAVA, Gold5

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

15686번: 치킨 배달

사용한 알고리즘 : 백트래킹, DFS를 통해 구현한 조합, 구현

 

풀이전략

문제에서 핵심은 기존의 모든 치킨집들 중에서 M개의 치킨집만 남겼을 때, 가장 최소의 치킨 거리를 구하는 것이다.

(치킨 거리란 모든 가정집에서 남김 특정 치킨집까지의 최소 거리 합을 뜻한다.)

 

 

1. 조합을 사용해 모든 치킨집들 중 M개의 치킨집을 선정한다.

2. 각 가정집에서 조합으로 구한 M개의 치킨집들과의 최소 치킨 거리를 구한다.

3. 1~2번 과정을 반복하여, 조합으로 나온 모든 부분집합과 각 가정집에서의 최소 치킨 거리 중

    가장 작은 값을 구한다. 그 값이 우리가 구하는 정답이다.

 

위 풀이 과정을 코드로 나타내면 아래와 같다.

 

1. 조합을 사용해 모든 치킨집들 중 M개의 치킨집을 선정한다.

// 검색이 자주 쓰이는건 ArryList, 추가/삭제가 자주 쓰이는건 LinkedList
static List<ChickenStore> chickenStores = new ArrayList<>(); // 모든 치킨집들의 좌표가 담김
static List<ChickenStore> subSetChickenStores = new LinkedList<>(); // 조합으로 나온 치킨집들 좌표 담을 것임

static void dfs(int current, int depth){
    if(depth==M){
        // 해당 치킨집만을 남겨두고 도시의 치킨 거리를 구함
        calculateDistance();
        return;
    }

    // 조합(치킨 집들 중 M개의 치킨집이 있을 때 연산을 하도록 함)
    for(int i=current;i<chickenStores.size();++i){
        subSetChickenStores.add(chickenStores.get(i));
        dfs(i+1,depth+1);
        subSetChickenStores.remove(depth);
    }
}

dfs를 사용해 조합을 구현한 모습이다.

depth는 부분집합에 담긴 원소들의 개수를 나타내는데, 이 수가 M이 되면 도시의 치킨 거리를 계산하고 함수를 종료한다.

 

2. 각 가정집에서 조합으로 구한 M개의 치킨집들과의 최소 치킨 거리를 구한다.

먼저 ChickenStore라는 클래스는 아래와 같이 구성되어 있다.

static class ChickenStore{
    int row;
    int col;

    public ChickenStore(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

아래는 이를 활용해 최소 치킨 거리를 구하는 코드이다.

static int map[][]; // 입력받은 지도가 담긴 배열
static int resultMinVal=Integer.MAX_VALUE; // 최소 치킨 거리를 담을 변수

static void calculateDistance(){
    int sum=0;
    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            if(map[i][j]==1){
                int minVal=Integer.MAX_VALUE;
                for(ChickenStore store:subSetChickenStores){ // 조합으로 선정한 치킨집들
                    minVal=Math.min(minVal,Math.abs(i-store.row)+Math.abs(j-store.col));
                }
                sum+=minVal; // (i,j)에 위치한 가정집에서 가장 가까운 치킨집까지의 거리를 더함
            }
        }
    }
    resultMinVal=Math.min(resultMinVal,sum);
}

map의 모든 가정집에서 조합으로 선정한 치킨집들과의 치킨 거리를 구한다.

이를 반복하여 가장 작은 치킨 거리를 resultMinVal에 저장하면 문제의 정답을 도출할 수 있다.

 

제출코드

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

public class Main {
    static int N,M;
    static int map[][];
    static int visited[][];
    static int tempMap[][];
    static List<ChickenStore> chickenStores = new ArrayList<>();
    static List<ChickenStore> subSetChickenStores = new LinkedList<>();
    static int resultMinVal=Integer.MAX_VALUE;
    static class ChickenStore{
        int row;
        int col;

        public ChickenStore(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
    static void dfs(int current, int depth){
        if(depth==M){
            // 해당 치킨집만을 남겨두고 도시의 치킨 거리를 구함
            calculateDistance();
            return;
        }

        // 조합(치킨 집들 중 M개의 치킨집이 있을 때 연산을 하도록 함)
        for(int i=current;i<chickenStores.size();++i){
            subSetChickenStores.add(chickenStores.get(i));
            dfs(i+1,depth+1);
            subSetChickenStores.remove(depth);
        }
    }

    static void calculateDistance(){
        int sum=0;
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                if(map[i][j]==1){
                    int minVal=Integer.MAX_VALUE;
                    for(ChickenStore store:subSetChickenStores){
                        minVal=Math.min(minVal,Math.abs(i-store.row)+Math.abs(j-store.col));
                    }
                    sum+=minVal;
                }
            }
        }
        resultMinVal=Math.min(resultMinVal,sum);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][N];

        for(int i=0;i<N;++i){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;++j){
                int val = Integer.parseInt(st.nextToken());
                if(val==1){
                    map[i][j]=val;
                }
                else if(val==2){
                    chickenStores.add(new ChickenStore(i,j));
                }
            }
        }

        dfs(0,0);

        bw.write(resultMinVal+"\n");
        bw.flush();
        bw.close();
    }
}