[백준] 15686번 치킨배달 - JAVA

---

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

15686번: 치킨 배달

 

 

구현 문제를 풀다 보면 삼성 기출을 자주 만난다.

해당 문제도 삼성 sw 역량테스트 기출문제다.

 

2차원이 나오면 bfs dfs를 의심하게 된다. 하지만 문제를 읽어보면

거리 계산은 단순 수식으로 할 수 있고

백트래킹 문제인 것을 알 수 있다.

 

주어진 M이 치킨집의 개수이니 

치킨집을 조합으로 선택해서 치킨 거리 MIN을 구해주면 끝이다.

 

처음 문제를 풀 때 M을 못 보고

1~N까지 조합 백 트래킹 하며 왜 안될까 생각했다.

 

문제를 잘 읽자

 

---

 

항상 주의할 점 문제를 잘 읽자

제공해주는 변수(입력)가 무엇인지 보자.

 

---

코드

 

import java.io.*;
import java.math.BigInteger; // subtract , multiply, add, mod
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int[][] arr;
    static int[] temp;
    static List<Node> clist;
    static List<Node> hlist;
    static int globalMin = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {

        // 입력부
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int size = Integer.parseInt(st.nextToken());
        int chicken = Integer.parseInt(st.nextToken());
        arr = new int[size][size];

        clist = new ArrayList<>();
        hlist = new ArrayList<>();
        for(int i = 0; i<size; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j<size; j++){
                int cHorHo = Integer.parseInt(st.nextToken());
                arr[i][j] = cHorHo;

                if(cHorHo == 2){ // 치킨집
                    clist.add(new Node(i+1, j+1));
                }else if( cHorHo ==1)
                    hlist.add(new Node(i+1, j+1));
            }
        }
        temp = new int[chicken];
        bt(chicken, 0, 0);
        System.out.println(globalMin);
        
    }public static void bt(int limit, int n , int idx){
        if(limit == n){
            int minSum = 0;
            int[] mins = new int[hlist.size()]; // 모든 집 min 저장
            Arrays.fill(mins, 10000);
            for(int i = 0 ; i<hlist.size(); i++){ // 집
                Node hnode = hlist.get(i);
                for(int j = 0; j<limit; j++){ // 치킨
                    Node cnode = clist.get(temp[j]);

                    int n1 = Math.abs(hnode.x - cnode.x) + Math.abs(hnode.y - cnode.y);

                    mins[i] = Math.min(mins[i], n1);
                }
            }
            for(int e : mins)
                minSum+=e;

            globalMin = Math.min(globalMin, minSum);
            return;
        }

        for(int i = idx ; i<clist.size(); i++){
            temp[n] = i;
            bt(limit, n + 1, i + 1);
        }
    }
}
class Node{
    int x;
    int y;
    public Node(int x, int y){
        this.x = x;
        this.y = y;
    }
    public String toString(){
        return this.x+" " + this.y;
    }
}