BOJ(15686) - 치킨 배달 (JAVA)

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

15686번: 치킨 배달

 

 

• 백트래킹 완전탐색으로 구할 수 있는 문제이다.
• 초반에 시간 초과로 꾀 고생을 했는데 집을 선택하는 순서는 관계 없기 때문에 오름 차순 식으로 풀면 통과 할 수 있다.
• 결론적으로 아래의 문제에서 입력 형식과 결과 도출만 달라진 문제였다.
  • N과 M(2)

 

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

public class Main {
    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int N, M;
    private static int minPathChickens = Integer.MAX_VALUE;
    private static List<Node> chickens = new ArrayList<>();
    private static List<Node> homes = new ArrayList<>();
    private static boolean[] visit;

    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());

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

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

                if (type == 2) {
                    chickens.add(new Node(i, j));
                } else if (type == 1) {
                    homes.add(new Node(i, j));
                }
            }
        }

        visit = new boolean[chickens.size()];
        dp(0, -1);
        System.out.println(minPathChickens);
    }

    private static void dp(int depth, int pre) {
        if (depth == M) {

            int total = 0;
            for (int i = 0; i < homes.size(); i++) {
                int minPathFromHome = Integer.MAX_VALUE;
                Node home = homes.get(i);
                for (int j = 0; j < visit.length; j++) {
                    if (visit[j]) {
                        Node chicken = chickens.get(j);
                        minPathFromHome = Math.min(minPathFromHome,
                                Math.abs(home.y - chicken.y) + Math.abs(home.x - chicken.x));
                    }
                }
                total += minPathFromHome;
            }
            minPathChickens = Math.min(minPathChickens, total);
            return;
        }

        for (int i = depth; i < chickens.size(); i++) {
            if (visit[i] == false && pre < i) {
                visit[i] = true;
                dp(depth + 1, i);
                visit[i] = false;
            }
        }
    }

    static class Node {
        public int y;
        public int x;

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