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

치킨 배달

이전에 풀었던 연구소 문제의 쉬운 버전? 그 정도 난이도였던 것 같다.

풀이

주의할 점은 좌표의 시작이 1부터라는 것이다. 그래서 일반적인 배열의 인덱스로 풀이하면 안된다.

풀이는 다음과 같다.

1. 입력받은 값에서 집(1)들을 배열에 따로 저장한다.
2. 입력받은 값에서 치킨집(2)들을 배열에 따로 저장한다.
3. 치킨집들을 저장한 배열에서 m개를 뽑는다.
4. 뽑은 m개의 치킨집에서 각 집들 사이의 거리를 구해 최소값들만 저장한다.
5. 최소값들을 합하여 도시 치킨 거리를 구한다.
6. 기존 ans 값과 비교 작은 값을 ans로 한다.
7. 저장해놓은 각 집에서 치킨집까지의 거리를 초기화한다.
8. 모든 경우를 탐색할 때까지 3-7을 반복한다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int ans = Integer.MAX_VALUE;
    static int n, m;
    static boolean[] visit;
    static int[][] graph;
    static ArrayList<Pair> chick;
    static ArrayList<Pair> house;
    static Pair[] selectedChick;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] first = br.readLine().split(" ");
        n = Integer.parseInt(first[0]);
        m = Integer.parseInt(first[1]);

        graph = new int[n + 1][n + 1];
        //visit = new boolean[n][m];
        chick = new ArrayList<>();
        house = new ArrayList<>();
        selectedChick = new Pair[m];

        for (int i = 1; i <= n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                int num = Integer.parseInt(line[j]);
                if (num == 2) {
                    chick.add(new Pair(i, j + 1, 0));
                } else if (num == 1) {
                    house.add(new Pair(i, j + 1, Integer.MAX_VALUE));
                }
            }
        }
        selectChick(0, 0);

        bw.write(ans+"\n");
        br.close();
        bw.close();
    }

    private static void calcDistance() {
        Queue<Pair> queue = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            Pair p = selectedChick[i];
            queue.offer(p);
        }

        while (!queue.isEmpty()) {
            Pair chick = queue.poll();
            for (int i = 0; i < house.size(); i++) {
                Pair home = house.get(i);
                int dis = Math.abs(chick.x - home.x) + Math.abs(chick.y - home.y);
                home.dist = Math.min(home.dist, dis);
            }
        }
        int temp = 0;
        for(Pair p : house) {
            temp += p.dist;
        }
        ans = Math.min(temp, ans);
    }

    private static void resetDistance() {
        for(Pair p :house)
            p.dist = Integer.MAX_VALUE;
    }

    private static void selectChick(int pos, int cnt) {
        if (cnt == m) {
            calcDistance();
            resetDistance();
            return;
        }
        for (int i = pos; i < chick.size(); i++) {
            selectedChick[cnt] = chick.get(i);
            selectChick(i + 1, cnt + 1);
        }
    }
}

class Pair {
    public int x;
    public int y;
    public int dist;

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