[BOJ] 백준 15686 - 치킨 배달 풀이

1. 문제

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

15686번: 치킨 배달

 

2. 풀이

백 트래킹 및 탐색을 이용하여 푸는 문제이다. 백 트래킹에 대한 내용이 기억이 나지 않아서 잘 정리된 블로그 포스팅을 참고하였고 다른분의 풀이를 참고하였다.

https://iseunghan.tistory.com/241

알고리즘 - 백트래킹(Back-Tracking)

우선 문제에서 입력으로 주어진 2차원 배열에서 집(1)의 좌표와 치킨집(2)의 좌표를 각각 List에 저장하고 백 트래킹 알고리즘을 사용하여 함수에 입력된 치킨집의 개수(cnt)가 입력으로 주어진 치킨집의 개수와 같을 때까지 start(백 트래킹의 시작점)와 cnt(치킨집의 개수)를 하나씩 증가시키며 재귀함수를 실행한다. cnt가 입력으로 주어진 치킨집의 개수와 같아진다면 거리를 계산하고 최소값을 갱신한다. 

백트래킹에 대한 이해가 아직 많이 부족한 것 같다... 

 

3. 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Main {

    static class Point {
        int x;
        int y;

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

    static int N;
    static int M;  // 치킨집의 최대 개수
    static int result; // 결과 값
    static int[][] map;
    static boolean[] open;

    static List<Point> chicken = new ArrayList<>();
    static List<Point> house = new ArrayList<>();

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

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

        result = Integer.MAX_VALUE;
        open = new boolean[chicken.size()];
        chicken(0, 0);

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

    private static void chicken(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 dist = Math.abs(house.get(i).x - chicken.get(j).x) + Math.abs(house.get(i).y - chicken.get(j).y);

                        temp = Math.min(temp, dist);
                    }
                }
                res += temp;
            }
            result = Math.min(res, result);
            return;
        }

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