자바(백준) 15686 치킨 배달

오답 노트 & 새로 알게 된 점

처음 접근 방식은 백트래킹을 이용하여 치킨집을 0으로 만들고 다시 2로 설정해서, 거리를 구하려고 했다. 하지만 여기서 어떻게 제일 가까운 거리를 구해야 할지 전혀 방법이 떠오르지 않았다. 물론, 포문을 여러 개 사용하여 거리를 구할 수 있지만 시간 복잡도를 보니 무조건 TLE가 나올 것 같아 새로운 방법을 생각해보았다. 하지만 방법이 떠오르지 않아 구글링을 하여 힌트를 얻었다. 

 

이러한 거리 계산이 나온다면 Point 클래스를 선언해주는 방법을 생각하자.  그리고 꼭 이차원 배열 안에서 생각하지 말자. 예를 들어 chicken과 home ArrayList를 만들어주어 좌표를 저장하는 방법. 어떻게 이런 생각을 하는지 정말 기발하다고 생각했다. 그리고 입력 순서대로 chicken, home ArrayList에 넣어주기 때문에 순서가 보장되어 visit 배열을 그대로 사용해도 된다는 점도 있다.

 

풀이 방법

1. 입력을 하면서 숫자가 1이면 home ArrayList에, 2면 chicken ArrayList에 저장을 한다.

 

1-2. 여기서 우리는 한 집(숫자 1)을 기준으로 여러 치킨 집에 대한 맨허튼 거리를 계산하고, 그중에 최솟값이 치킨 거리이다. 그래서 visit 배열을 사용하여 철거하지 않은 치킨집을 true로 한다. 그래서 visit배열의 크기는 chicken ArrayList의 size와 같다.

 

2. 백트래킹 메소드에서 visit 배열을 true로 하고 재귀 함수를 부르는 것은 어느 백트래킹 문제와 같다.

 

3. 이제 depth와 M(치킨집 갯수)가 같을 때 생각해보자.

 

3-1. 집을 기준으로 각각 치킨집들과의 거리를 계산해야 한다. 그중에 가장 최솟값이 치킨 거리이다. 따라서 기준을 i(집)으로 잡고 j로 각각 치킨집과의 맨해튼 거리를 계산한다. 그리고 temp를 이용하여 그중 최솟값을 temp에 저장한다. 

 

3-2. temp는 이제 한 집에서의 치킨 거리를 나타낸다. 그리고 이제 sum을 이용하여 각 치킨 거리의 합 즉, 도시의 치킨 거리를 구한다. 이 부분은 이제 치킨 거리가 1 2 3일 때 최솟값을 갖는지, 1 2 4일 때 최솟값을 갖는지 비교하는 것이다. 따라서 min이 도시의 치킨 거리의 최솟값이다.

 

사용 개념

재귀 함수, Point 클래스

 

코드

package BackTracking;
 
import java.io.*;
import java.util.*;
 
public class Main {
    static int arr[][];
    static int N, M;
    static ArrayList<ChicPoint> home = new ArrayList<>();
    static ArrayList<ChicPoint> chicken = new ArrayList<>();
    static boolean visit[];
    static int min = Integer.MAX_VALUE;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        arr = new int[N][N];
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                int num = Integer.parseInt(st.nextToken());
                arr[i][j] = num; // ---------------- 1
                if(num == 1) home.add(new ChicPoint(i,j));
                else if(num == 2) chicken.add(new ChicPoint(i,j));
            }
        }
        visit = new boolean[chicken.size()]; // ----- 1-2
 
        backTracking(0,0);
        System.out.print(min);
    }
 
    static void backTracking(int start, int depth){
        if(depth == M){ // --------------------------- 3
            int sum = 0;
            int distance = 0;
            for(int i = 0; i < home.size(); i++){
                int temp = Integer.MAX_VALUE;
                for(int j = 0; j < chicken.size(); j++){
                    if(visit[j]){
                        distance = checkDistance(home.get(i), chicken.get(j));
                        // ----------------- 3-1
                        temp = Math.min(temp, distance);
                    }
                }
                sum += temp;
            }
            min = Math.min(sum, min);
            return;
        }
        for(int i = start; i < chicken.size(); i++){ // ------------2
            if(visit[i]) continue;
 
            visit[i] = true;
            backTracking(i + 1, depth + 1);
            visit[i] = false;
        }
    }
 
    static int checkDistance(ChicPoint a, ChicPoint b){
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }
}
 
class ChicPoint{
    int x, y;
    ChicPoint(int x, int y){
        this.x = x;
        this.y = y;
    }
}