BOJ 15686 치킨 배달

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

15686번: 치킨 배달

 

1. 아이디어

1. map을 돌면서 집과 치킨집의 좌표를 저장

2. 저장해둔 리스트에서 치킨 집을 M개 선택 - 중복없이 순서 상관 없이 뽑는 조합문제

2. 각 경우마다 치킨 거리를 구해 최솟값 갱신

 

 

처음에 map을 보자마자 고정관념으로 map 전체를 돌면서 완전탐색을 해야할 거라고 생각했는데 그렇게 하면 너무 복잡해진다. 어짜피 거리를 구하는 문제이기 때문에 거리 구하는 공식이 있어서 map과 상관없이 좌표만 알면 답을 구할 수 있다. 그래서 map은 신경 안쓰고 집과 치킨집의 좌표를 리스트화해서 단순 조합 문제로 바꿀 수 있다. 풀다가 모르겠어서 풀이를 본 문제인데 매우 경이롭다.. 이런 생각들을 어떻게 하는건지..

 

만약 map에서 장애물이 있어서 못가는 루트가 있다면 map을 완전탐색하는 방법을 생각해봐야 할 것이다.

 

2. 시간복잡도

범위: N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)

 

NxM map에서 M개를 뽑는 조합문제이므로 시간복잡도는 O((50*13)!)보단 작다. 

 

3. 구현

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static int N, M;
    static int[][] map;
    static int answer = Integer.MAX_VALUE;
    static ArrayList<Pair> house = new ArrayList<>();
    static ArrayList<Pair> chicken = new ArrayList<>();
    static int[] selected;

    static class Pair {
        int x, y;

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

    public static void init() throws IOException {
        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                int a = Integer.parseInt(st.nextToken());
                if (a == 1) {
                    house.add(new Pair(i, j));
                } else if (a == 2) {
                    chicken.add(new Pair(i, j));
                }
            }
        }

//        System.out.println("치킨집 수: " + chicken.size());

        selected = new int[M + 1];
    }

    private static void print(ArrayList<Pair> arr) {
        Iterator<Pair> iterator = arr.iterator();
        while (iterator.hasNext()) {
            Pair p = iterator.next();
            System.out.println(p.x +" , " + p.y);
        }
    }

    public static void main(String[] args) throws Exception {
        init();

        rec_func(1, 0);

        System.out.println(answer);

        br.close();
        bw.close();
    }

    private static void rec_func(int k, int prev) {
        if (k == M + 1) {
            int sum = 0;

            for (int i = 0; i < house.size(); i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 1; j <= M; j++) {
                    Pair p1 = house.get(i);
                    Pair p2 = chicken.get(selected[j]);

                    min = Math.min(min, Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y));

                }
//                System.out.println("min값: " + min + "i값: " + i);
                sum += min;
            }

//            System.out.println("케이스: " + sum+" ");
            answer = Math.min(answer, sum);

        } else {
            for (int i = prev; i < chicken.size(); i++) {
                selected[k] = i;
                rec_func(k + 1, i + 1);

            }
        }
    }
}