백준 15686 자바 (치킨 배달)

<문제>

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

15686번: 치킨 배달

<풀이>

 

이 문제 같은 경우 기존에 풀었던 것처럼 dx, dy를 사용해서 문제를 푸려고 했으나, 4방향으로 탐색할 때 조건이 명확하지 않다. 

또한 치킨집과 집을 따로 보관해야 하기때문에 2개의 List를 이용해서 문제를 해결한다.

입력할 때 집은 집끼리 List에 저장하고 치킨 집은 치킨집끼리 List에 저장한다.

이러고 나서 DFS를 치킨집 리스트를 기준으로 탐색을 진행한다.

치킨집 위치가 저장되어 있는 List 중에서 M개를 선택하는 DFS를 만들고 M개를 선택했을 때 집의 위치와 치킨집의 위치를 다 더해서 그중에 치킨 거리가 제일 작은 값을 출력하면 된다.

이때 치킨집이 오픈하는지 안하는지는 boolean배열을 이용해서 치킨집이 폐업하는 곳인지 아닌지를 선택하게 한다.

 

<코드>

 

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

public class Main {
    public static int n;
    public static int m;
    public static int[][] map;
    public static boolean[] open;
    public static int ans;
    public static ArrayList<Point> chicken = new ArrayList<>();
    public static ArrayList<Point> house = new ArrayList<>();

    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];
        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 Point(i,j));
                }
                else if (map[i][j] == 2) {
                    chicken.add(new Point(i,j));
                }
            }
        }
        ans = Integer.MAX_VALUE;
        open = new boolean[chicken.size()];
        dfs(0,0);
        System.out.println(ans);
    }

    public static void dfs(int start, int cnt) {
        if (cnt == m) {
            int res = 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).x - chicken.get(j).x)
                                + Math.abs(house.get(i).y - chicken.get(j).y);
                        temp = Math.min(temp, distance);
                    }
                }
                res += temp;
            }
            ans = Math.min(ans,res);
            return;
        }

        for(int i = start; i < chicken.size(); i++) {
            open[i] = true; // 치킨집 폐업
            dfs(i + 1, cnt + 1);
            open[i] = false; // 3개를 찾고 난 이후에는 폐업했던 치킨집 폐업을 취소한다.
        }
    }
}

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