[BOJ] 15686 -치킨 배달(G5)

문제 링크

15686-치킨 배달

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

문제 풀이

백트래킹 문제
백트래킹 + 조합으로 해결

집의 위치와 치킨집의 위치를 Node 클래스를 만들어 위치를 저장했고
뽑은 m개의 치킨집은 boolean 일차원 배열을 통해서 뽑았는지의 여부를 표시

m개를 뽑고 난 후 for문을 통해 집의 위치에서부터 치킨거리를 구해 도시의 치킨거리를 구해줌
완전탐색으로 하나하나 확인하며 구해줘도 시간초과 나지 않아서
굳이 bfs를 사용하지 않았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Node {
    int x, y;

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

public class Main {
    static int N, M, min = Integer.MAX_VALUE;
    static int[][] maps;
    static ArrayList<Node> houses = new ArrayList<>();
    static ArrayList<Node> chicken = new ArrayList<>();
    static boolean[] visited;

    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());
        maps = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                maps[i][j] = Integer.parseInt(st.nextToken());
                if (maps[i][j] == 1) {
                    houses.add(new Node(i, j));
                } else if (maps[i][j] == 2) {
                    chicken.add(new Node(i, j));
                }
            }
        }

        visited = new boolean[chicken.size()];
        back(0, 0);
        System.out.println(min);
    }

    public static void back(int depth, int start) {
        if (depth == M) {
            int total = 0;
            for (int i = 0; i < houses.size(); i++) {
                int tmp = Integer.MAX_VALUE;
                for (int j = 0; j < chicken.size(); j++) {
                    if (visited[j] == true) {
                        int dist = Math.min(min, Math.abs(houses.get(i).x - chicken.get(j).x) + Math.abs(houses.get(i).y - chicken.get(j).y));
                        tmp = Math.min(tmp, dist);
                    }
                }
                total += tmp;
            }
            min = Math.min(total, min);
        }

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