백준 15686번 : 치킨 배달 (Java)

🔗 문제 링크

15686번: 치킨 배달

---

📖 풀이 과정

- 백트래킹을 활용한 구현 문제입니다.

- 배열의 값을 입력 받을 때 치킨집에 해당하는 값을 치킨리스트에, 집에 해당하는 값을 집 리스트에 담습니다.

- 이후, 백트래킹 방식을 활용하여 치킨 리스트에 있는 값들을 순회합니다.

- 만약 인덱스 값이 m값이 된다면, 그때서야 집 리스트에 있는 값들과 순회하면서 치킨 거리 및 도시의 치킨 거리값을 구합니다.

- 구한 도시의 치킨 거리의 최소값을 갱신하면서 문제를 진행합니다.

- 문제를 풀이하며 제가 여러번 실수한 부분이 있어서 공유합니다.
  - 백트래킹 방식을 진행할 때 for문의 인덱스에 신경을 못써서 재귀 메소드 호출시 값을 i를 이용하지 않고 start 변수를 이용했습니다.
  - 이렇게 할 경우, 답을 구하는 것은 문제가 되지 않지만 시간 초과가 발생합니다.
  - 따라서, for문으로 한번에 모두 순회할 수 있도록 인덱스를 신경 써줘야 합니다.

---

💻 코드

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int[][] arr;
    static boolean[] visited;
    static int n, m, answer;
    static ArrayList<Point> home;
    static ArrayList<Point> chicken;

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

        home = new ArrayList<>();
        chicken = new ArrayList<>();
        arr = new int[n][n];

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

                if (arr[i][j] == 1) {
                    home.add(new Point(i, j));
                } else if (arr[i][j] == 2) {
                    chicken.add(new Point(i, j));
                }
            }
        }

        answer = Integer.MAX_VALUE;
        visited = new boolean[chicken.size()];

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

    public static void solve(int start, int depth) {
        if (depth == m) {
            int res = 0;

            for (int i = 0; i < home.size(); i++) {
                int temp = Integer.MAX_VALUE;
                for (int j = 0; j < chicken.size(); j++) {
                    if (visited[j]) {
                        int dist = Math.abs(home.get(i).x - chicken.get(j).x)
                                + Math.abs(home.get(i).y - chicken.get(j).y);

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

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

    static class Point {
        int x, y;

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