[백준][Java] 15686번 : 치킨배달

[문제 링크]

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

---

문제 설명

0-빈칸, 1-집, 2-치킨집
치킨거리 = 집(x1, y1)과 가장 가까운 치킨집(x2, y2) 사이의 거리 → |(x1-x2)| + |(y1-y2)|
도시의 치킨거리 = 모든 집의 치킨 거리의 합
치킨집을 최대 m개를 골랐을 때, 도시의 치킨거리의 최소값을 구한다.

 

 

 

 

 

 

문제 풀이

• 도시에 대한 정보를 입력받으면서 치킨집과 집의 위치 정보를 리스트에 따로 저장한다.
• dfs( ) : dfs 알고리즘을 사용해서 m개의 치킨집을 고른다. 이 때, 치킨집의 위치를 따로 저장한 리스트를 사용해서 m개의 치킨집을 고른다.
• houseChicken( ) : 하나의 집에 대해서 m개의 치킨집을 돌면서 거리가 가장 가까운 치킨집과의 치킨거리를 구한다.
• cityChicken( ) : houseChicken() 에서 구한 치킨거리를 모두 더해서 도시의 치킨거리를 구한다. 그리고 도시의 치킨거리의 최솟값을 구한다.

 

전체 코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;


class Position {
    int x;
    int y;

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

public class Main {

    static int n, m, result;
    static int cityMin = Integer.MAX_VALUE;
    static int[][] cities;
    static int[] choose;	//선택한 m개의 치킨집
    static ArrayList<Position> chicken = new ArrayList<>();	//치킨집의 위치 정보
    static ArrayList<Position> house = new ArrayList<>();	//집의 위치 정보


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());   //도시의 크기
        m = Integer.parseInt(st.nextToken());   //폐업시키지 않을 치킨집의 최대 개수

        cities = new int[n][n];
        choose = new int[m];
        //도시 정보 입력
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                cities[i][j] = Integer.parseInt(st.nextToken());
                //치킨집의 위치 정보 저장
                if (cities[i][j] == 2) {
                    chicken.add(new Position(i, j));
                }

                //집의 위치 정보 저장
                if(cities[i][j] == 1)
                    house.add(new Position(i, j));
            }

        }

        dfs(0, 0);
        System.out.println(result);
    }

    public static void dfs(int cnt, int start) {
        //종료조건 : 고른 치킨집의 개수가 m인 경우
        if (cnt == m) {
            result = cityChicken();
            return;
        }

        for (int i = start; i < chicken.size(); i++) {
            choose[cnt] = i;	//선택한 치킨집의 인덱스 저장
            dfs(cnt + 1, i + 1);
        }
    }

    //도시의 치킨거리의 최솟값 구하는 메서드
    public static int cityChicken() {
        int sum = 0;
        for (int i = 0; i < house.size(); i++) {
            int houseMin = houseChicken(house.get(i));
            sum += houseMin;
        }

        cityMin = Math.min(cityMin, sum);
        return cityMin;
    }

    //각 집의 치킨거리를 구하는 메서드
    public static int houseChicken(Position position) {
        int houseMin = Integer.MAX_VALUE;
        int houseX = position.x;
        int houseY = position.y;

        for (int i = 0; i < choose.length; i++) {
            int chickenX = chicken.get(choose[i]).x;
            int chickenY = chicken.get(choose[i]).y;

            int distance = Math.abs((houseX - chickenX)) + Math.abs((houseY - chickenY));
            houseMin = Math.min(houseMin, distance);
        }
        return houseMin;
    }
}