[Algo] 백준 15686 치킨 배달 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/15686

메모리 : 17312KB

시간 : 236ms

언어 : Java 11

---

코드

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

public class Main {
    static class Node {
        int r, c;

        Node(int r, int c) {
            this.r = r;
            this.c = c;
        }

    }

    static List<Node> chicken = new ArrayList<>();
    static List<Node> home = new ArrayList<>();
    static boolean[] check;
    static int N, M, hl, cl, ans;

    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());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int num = Integer.parseInt(st.nextToken());
                if (num == 1) {
                    home.add(new Node(i, j));
                } else if (num == 2) {
                    chicken.add(new Node(i, j));
                }
            }
        }
        hl = home.size();
        cl = chicken.size();
        check = new boolean[20];
        ans = Integer.MAX_VALUE;
        dfs(0, 0);
        System.out.println(ans);
    }

    private static void dfs(int idx, int d) {
        if (d == M) {
            int sum = 0;
            for (int i = 0; i < hl; i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 0; j < cl; j++) {
                    if (check[j]) {
                        int tmp = Math.abs(home.get(i).r - chicken.get(j).r)
                                + Math.abs(home.get(i).c - chicken.get(j).c);
                        min = Math.min(min, tmp);
                    }
                }
                sum += min;
            }
            ans = Math.min(sum, ans);
            return;
        }
        //idx부터 뒤로 탐색해야 시간절약이 가능하다.
        //idx는 1씩 늘어나고, 치킨집 수많큼 탐색하기때문에 직삼각형꼴로 순회한다.
        for (int i = idx; i < cl; i++) {
            check[i] = true;
            dfs(i + 1, d + 1);
            check[i] = false;
        }

    }
}

 

풀이

bfs로 시도하다가 불가능임을 알고.. 황급히 dfs로 전환했다 ㅎㅎ 치킨과 집의 위치를 Node로 각각 저장해놓고, M개의 치킨집을 골라 거리를 재고, 최소일 때를 저장해 갱신한다. 배열이 50*50이고, M도 13이라서 아무생각없이 조합을 만들면 시간초과가 난다. 배열을 순회할 때 최소가 되도록 설계해야한다.