[BOJ] 15686. 치킨 배달

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

접근 방법

입력 값에서 그냥 ArrayList에 집 and 치킨집을 넣어주었다.

그리고 치킨집에 대해서는 아직 개장을 한지 안한지에 대해서 state 필드를 주었다.

그리고 치킨집을 하나 고를 때 마다 문제에서 원했던 ' 치킨 거리 ' 를 구하고 답에 계속 최소인지 확인하면서 대입을 해주었다.

주의 사항

1. 치킨 집을 하나씩 넣어줄 때 (0,1) (2,0) 은 (2,0) (0,1) 은 중복이 된다. 이 중복을 없애자.

   또한 for(int i=start; i<chickenLoc.size(); i++) 여기에서 i = start를 하지 않으면 안된다!!!

   이 의미에 대해서는 곰곰히 생각하고 왜 불필요한지에 대해서 이해를 하면 될 것 같다.

    static void getAllDistance(int start, int cnt, int bit){
            if(cnt == M){
                visit[bit] = true;
    //            printChickenLoc();
                int temp = getCityChickenDistance();
    //            System.out.println(" -> distance : " + temp + " and bit is " + bit);
                ans = Math.min(temp, ans);
            }
            for(int i=start; i<chickenLoc.size(); i++){
                if(chickenLoc.get(i).state || visit[bit|1<<i]) continue;
                chickenLoc.get(i).state = true;
                getAllDistance(i,cnt+1, bit|1<<i);
                chickenLoc.get(i).state = false;
            }
        }

Need Know

1. 구현!

전체 코드 ( Java )

import java.io.*;
import java.util.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int M;
    static int[][] map;
    static ArrayList<Location> chickenLoc;
    static ArrayList<Location> homeLoc;
    static final int HOME = 1;
    static final int CHICKEN = 2;
    static int ans = Integer.MAX_VALUE;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        set();
        solve();
        bw.flush();
        bw.close();
        br.close();
    }

    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        chickenLoc = new ArrayList<>();
        homeLoc = new ArrayList<>();
        for(int i=0;i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int k=0; k<N;k++){
                map[i][k] = Integer.parseInt(st.nextToken());
                if(map[i][k] == CHICKEN) {
                    chickenLoc.add(new Location(i,k,false));
                }
                if(map[i][k] == HOME){
                    homeLoc.add(new Location(i,k));
                }
            }
        }
        visit = new boolean[1<<13+1];
    }
    static void printChickenLoc(){
        for(int i=0; i<chickenLoc.size(); i++){
            if(chickenLoc.get(i).state){
                System.out.print("(" +chickenLoc.get(i).x  + "," + chickenLoc.get(i).y +")"+" ");
            }
        }
    }
    static void printAllChickenLoc(){
        for(int i=0; i<chickenLoc.size(); i++){

                System.out.print("(" +chickenLoc.get(i).x  + "," + chickenLoc.get(i).y +")"+" ");
        }
    }
    static void solve() throws IOException {
//        printAllChickenLoc();
        if(chickenLoc.size()==M){
            // 모두 개장 시키자!
            for(int i=0; i<chickenLoc.size(); i++){
                chickenLoc.get(i).state = true;
            }
            ans = getCityChickenDistance();
        }else{
            getAllDistance(0,0,0);
        }
        bw.write(ans + "");

    }
    static void getAllDistance(int start, int cnt, int bit){
        if(cnt == M){
            visit[bit] = true;
//            printChickenLoc();
            int temp = getCityChickenDistance();
//            System.out.println(" -> distance : " + temp + " and bit is " + bit);
            ans = Math.min(temp, ans);
        }
        for(int i=start; i<chickenLoc.size(); i++){
            if(chickenLoc.get(i).state || visit[bit|1<<i]) continue;
            chickenLoc.get(i).state = true;
            getAllDistance(i,cnt+1, bit|1<<i);
            chickenLoc.get(i).state = false;
        }
    }
    static int getCityChickenDistance(){
        int cityChickenDistance = 0;
        for(int i=0; i<homeLoc.size(); i++){
            cityChickenDistance += getChickenDistance(homeLoc.get(i));
        }
        return cityChickenDistance;
    }
    static int getDistance(int x1, int y1, int x2, int y2){
        return (Math.abs(x1-x2)+Math.abs(y1-y2));
    }
    static int getChickenDistance(Location homeLoc){
        int chickenDistance = Integer.MAX_VALUE;
        for(int i=0; i<chickenLoc.size(); i++){
            // 개장 되어 있는 치킨집에 대해서만 구하기
            if(chickenLoc.get(i).state) {
                int distance = getDistance(homeLoc.x, homeLoc.y, chickenLoc.get(i).x, chickenLoc.get(i).y);
                if (chickenDistance > distance) chickenDistance = distance;
            }
        }
        return chickenDistance;
    }
}
class Location{
    int x,y;
    boolean state;

    public Location(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public Location(int x, int y, boolean state) {
        this.x = x;
        this.y = y;
        this.state = state;
    }
}