[백준 15686번 / java] 치킨 배달

문제

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

풀이1

(잘못된 접근)

치킨거리의 합이 가장 적도록 하려면 치킨집이 몇 번 선택되었는지 세어서 가장 많이 선택받은 치킨집 순서로 내림차순 정렬한 후, 앞에서부터 M개의 치킨집을 선택하는 방법으로 해를 구하려고 했다.

 

그러나 이 방법은 잘못된 접근이다. 치킨집이 많이 선택된다고 해서 치킨 거리의 총합이 최소화되지는 않는다. 

이 문제는 dfs로 M개의 모든 치킨집의 조합을 고려하여 가장 작은 치킨 거리를 찾아야 한다.

 

(올바른 풀이를 보려면 풀이2 참고)

집마다 집, 치킨집 사이의 최단경로 구하기 -> 최단을 만족하는 치킨집 count++

-> count 기준 내림차순 정렬 -> 앞에서부터 M개 고르기 -> 치킨거리 최솟값 출력

최단거리는 bfs로 구하는 것이 효율적이므로, 모든 좌표를 돌면서 해답을 찾아야겠다는 생각까지 떠올렸다.

 

알고리즘 유형을 확인해보니 브루트포스, 백트래킹이었다.

• 브루트 포스 : 완전탐색으로 해가 될만한 모든 경우를 탐색해서 후보를 찾은 후 해를 도출
• 백트래킹 : 완전탐색에서 해가 될 수 없는 겨우를 제외하고 가지치기를 하여 다른 경우 탐색

1. 집, 치킨집의 좌표를 찾아서 리스트에 삽입한다. 

집 : (1, 4) (2, 1) (2, 3) ... -> house 리스트에 삽입

치킨집 : (1, 2) (5, 5) -> chicken 리스트에 삽입

타입이 좌표이므로 리스트로 구현했다.

 

2. 집마다 모든 치킨집과의 거리를 구한다. 집 (1, 4)의 경우 다음과 같다.

(1, 4) (1, 2) -> 2

(1, 4) (5, 5) -> 5

집 (1, 4)의 치킨거리는 2

치킨집 (1, 2)의 count++

 

3. chicken리스트를 count 기준 내림차순 정렬, M개 선택

4. 최소 치킨 거리 도출

코드1

이 코드는 마지막으로 mindist가 갱신될 때마다 c.count++를 해주지 않기 때문에 위 풀이에 대한 정확한 결과가 도출되지 않는다.

//잘못된 접근
import java.io.*;
import java.util.*;

public class boj_15686 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        //좌표 입력 받기
        int[][] board = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //집, 치킨집 좌표 구하기
        List<House> house = new ArrayList<>();
        List<Chicken> chicken = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if(board[i][j] == 1){
                    house.add(new House(i, j));
                }
                if(board[i][j] == 2){
                    chicken.add(new Chicken(i, j, 0, 0));
                }
            }
        }
        //최소 거리 구하기
        for(int i=0; i<house.size(); i++){
            House h = house.get(i);
            int mindist = Integer.MAX_VALUE;
            for(int j=0; j<chicken.size(); j++){
                Chicken c = chicken.get(j);
                int dist = Math.abs(h.x-c.x) + Math.abs(h.y-c.y);
                if(dist < mindist){
                    mindist = dist;
                    c.count++;
                    c.dist = mindist;
                }
            }
        }
        Collections.sort(chicken);
        int ans = 0;
        for(int i=0; i<M; i++){
            ans += (chicken.get(i)).dist;
        }
        bw.write(ans+" ");
        bw.flush();
        bw.close();
    }
}
class House{
    int x, y;
    public House(int x, int y){
        this.x = x;
        this.y = y;
    }
}
class Chicken implements Comparable<Chicken>{
    int x, y, count, dist;
    public Chicken(int x, int y, int count, int dist){
        this.x = x;
        this.y = y;
        this.count = count;
        this.dist = dist;
    }
    public int compareTo(Chicken c){
        return c.count - this.count;
    }
}

풀이 2

도시의 모든 치킨집 중 M개의 치킨집을 고른 후, 각각의 경우 도시의 치킨 거리를 구한다.

그 중 가장 작은 값을 출력한다.

-> 브루트 포스 : 도시를 완전탐색하며 해가 될 수 있는 경우를 모두 실행한다. 얻어진 모든 결과들을 통해 답을 도출한다.

-> 백트래킹 : 완탐에서 해가 되지 않는 경우를 조건으로 걸러서 실행하지 않고, 분기하여 다음 경우의 수로 넘어감

코드 2

import java.io.*;
import java.util.*;
class Point {
    int x;
    int y;

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

public class boj_15686 {
    static int N, M;
    static int[][] board;
    static ArrayList<Point> house;
    static ArrayList<Point> chicken;
    static int ans;
    static boolean[] check;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        board = new int[N][N];
        house = new ArrayList<>();
        chicken = new ArrayList<>();

        //좌표 입력받기
        //집, 치킨집의 좌표를 list에 삽입
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 1) {
                    house.add(new Point(i, j));
                } else if (board[i][j] == 2) {
                    chicken.add(new Point(i, j));
                }
            }
        }

        ans = Integer.MAX_VALUE;
        check = new boolean[chicken.size()];

        DFS(0, 0);
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static void DFS(int start, int cnt) {
        //start: 다음에 탐색할 치킨집 인덱스
        //cnt: 현재까지 선택된 치킨집의 수
        //M개의 치킨집이 선택됨 -> 도시의 치킨거리 계산
        if (cnt == M) {
            //집과 선택된 치킨집의 거리를 구해서 최솟값 도출
            int sum = 0;
            //sum: 도시의 치킨거리
            for (int i = 0; i < house.size(); i++) {
                int mindist = Integer.MAX_VALUE;
                for (int j = 0; j < chicken.size(); j++) {
                    if (check[j]) {
                        int dist = Math.abs(house.get(i).x - chicken.get(j).x)
                                + Math.abs(house.get(i).y - chicken.get(j).y);
                        mindist = Math.min(mindist, dist);
                    }
                }
                sum += mindist;
            }
            ans = Math.min(ans, sum);
            return;
        }

        //백트래킹으로 모든 M개의 치킨집의 조합을 구해서 도시의 치킨거리 구하기
        //백트래킹 : start 이후의 치킨집만 선택하게 함 -> dfs탐색 시 중복 조합이 생기지 않도록 함(불필요한 탐색 줄이기)
        for (int i = start; i < chicken.size(); i++) {
            //check[]: 치킨집 방문 체크
            //cnt: 현재까지 선택된 치킨집의 수
            check[i] = true; //현재 치킨집을 선택
            DFS(i + 1, cnt + 1); //다음 치킨집을 선택
            check[i] = false; //현재 치킨집 선택 해제하고 다음 탐색을 위해 준비
        }
    }

}

Note

• 정말 너무 오래 걸렸던 문제이다. 백트래킹과 브루트포스의 개념부터 정리하며 다시 풀었다. 
• 코드의 어떤 부분이 백트래킹과 브루트포스를 구현하고 있는지 이해하자.
• 문제를 읽고 어떻게 풀어야 하는지 떠올린 후 그에 맞는 알고리즘을 함께 생각해낼 수 있도록 하자. 이전에 공부했던 문제의 코드 구조가 대략 떠오를 수 있도록

참고 블로그: https://velog.io/@kimmjieun/%EB%B0%B1%EC%A4%80-15686%EB%B2%88-%EC%B9%98%ED%82%A8-%EB%B0%B0%EB%8B%AC-Java-%EC%9E%90%EB%B0%94

[백준] 15686번 치킨 배달 - Java, 자바