백준 15686_치킨 배달_JAVA

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

15686번: 치킨 배달

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

public class Main {
    static int N, M; // N -> 가로 세로 길이, M -> 치킨집 최대 갯수
    static int[][] grid; // 맵
    static ArrayList<int[]> house = new ArrayList<>(); // 집 좌표
    static ArrayList<int[]> chicken = new ArrayList<>(); // 치킨집 좌표
    static boolean[] visited; // 치킨집 조합을 위해 만든 치킨 방문 확인 array
    static ArrayList<int[]> chickenChoise = new ArrayList<>(); // 치킨 조합 저장
    static int result = Integer.MAX_VALUE;

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

        grid = new int[N][N];

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

                if (grid[i][j] == 1) {
                    house.add(new int[]{i, j});
                }

                if (grid[i][j] == 2) {
                    chicken.add(new int[]{i, j});
                }
            }
        }

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

        backtracking(0, 0);

        System.out.println(result);

    }

    private static void backtracking(int chickenCount, int start) {
        if (chickenCount == M) {
            int sum = 0;

            for (int[] h : house) {
                int min = Integer.MAX_VALUE;  // 최단 거리
                for (int[] c : chickenChoise) { // 치킨 조합에 대해 모두 계산
                    int dis = Math.abs(h[0] - c[0]) + Math.abs(h[1] - c[1]); // 치킨집과 집 거리 계산
                    min = Math.min(dis, min);
                }
                sum += min; // 각 집마다 최소 치킨 거리 합산
            }
            result = Math.min(result, sum);
            return;
        }

        // 조합 구성
        for (int i = start; i < chicken.size(); i++) {
            if (!visited[i]) {// 방문 하지 않았을때
                visited[i] = true; // 치킨 집 선택
                chickenChoise.add(chicken.get(i)); // 선택한 치킨 집 조합에 추가
                backtracking(chickenCount + 1, i + 1); // 다음 치킨집 호출하기 위해 재귀
                chickenChoise.remove(chickenChoise.size() - 1); // 재귀를 다 돌고 나오면 방금 추가한 치킨 삭제
                visited[i] = false;
            }
        }
    }
}

 

회고 

- 백트랙킹을 사용하여 푸는 것은 알았는데 구현하는 부분에서 애를 먹었다

- 다시 한 번 풀어봐야겠다