백준 15686 자바

<문제>

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

15686번: 치킨 배달

 

<풀이>

맨 처음에 생각해 낸 방법은 치킨집 고르는 함수와 골랐을 때 최단거리 탐색하는 함수로 풀으려 했으나, 시간초과가 났다. 

백트레킹을 이용해서 dfs로 한번에 풀어보니 정답을 구할 수 있었다.

 

집의 위치와 치킨집의 위치를 리스트에 저장해 놓고 dfs에서 탐색한다. 치킨집리스트에서 치킨집 M개를 골랐을 때 집의 위치와 치킨집의 위치를 다 비교해서 거리가 제일 짧은 것을 더한 후 저장한다. 모든 경우의 수를 따져서 가장 거리가 짧은 거리를 구하면 된다.

 

<코드>

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

public class Main {

    public static int n;
    public static int m;
    public static int result;
    public static int[][] map;
    public static boolean[] open;
    public static ArrayList<int[]> house;
    public static ArrayList<int[]> chicken;


    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());

        map = new int[n][n];
        house = new ArrayList<>();
        chicken = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j  = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                if(map[i][j] == 1) house.add(new int[] {i,j});
                else if(map[i][j] == 2) chicken.add(new int[] {i,j});
            }
        }
        result = Integer.MAX_VALUE;
        open = new boolean[chicken.size()];
        dfs(0,0);
        System.out.println(result);
    }
    public static void dfs(int start, int cnt) {
        if (cnt == m) {
            int totalDistance = 0;
            for(int i = 0; i < house.size(); i++) {
                int temp = Integer.MAX_VALUE;
                for(int j = 0; j < chicken.size(); j++) {
                    if(open[j]) {
                        int distance = Math.abs(house.get(i)[0] - chicken.get(j)[0])
                                + Math.abs(house.get(i)[1] - chicken.get(j)[1]);
                        temp = Math.min(temp, distance);
                    }
                }
                totalDistance += temp;
            }
            result = Math.min(totalDistance, result);
            return;
        }

        for(int i = start; i < chicken.size(); i++) {
            open[i] = true;
            dfs(i + 1, cnt + 1);
            open[i] = false;
        }
    }
}

맨 아래 for문이 백트레킹 하는 과정이다. 치킨집을 선택했으면 open 배열에 해당 치킨집과 같은 Index를 가진 곳을 true로 바꿔준 후에 이후 다시 false로 바꿔줘야지 M개만큼 개수를 샌 후에 해당 위치는 선택하지 않은 상태로 바뀌고 다른 치킨집을 선택할 수 있다.