87강 피자 배달 거리 (백준 15686_치킨 배달)

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

 

문제

N*N 크기의 도시지도가 있다. 각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현된다. 각 격자칸은 좌표(행번호, 열번호)로 표시된다. 도시에는 각 집마다 피자배달거리가 있는데, 각 집의 피자 배달 거리는 해당 집과 도시에 존재하는 피자집들과의 거리중 최솟값이다. 

그런데 경기가 불황이라 도시에 있는 피자 집 중에서 M개만 남기고 나머지는 보조금을 주고 폐업시키려고한다. 

이때 M개의 피자집을 고르는 기준은 도시의 피자 배달 거리가 최소가 되는 값이다. 

도시의 피자 배달거리란 각 집들의 피자 배달 거리를 모두 합한 값이다. 

 

 

입력

첫번째 줄에 N과 M이 주어진다. 

두번째줄 부터 도시 정보가 입력된다.

 

출력 

첫째줄에 M개의 피자집이 선택되었을때 , 도시의 최소 배달 거리를 출력한다. 

 

 

입력 예시 

4 4
0 1 2 0
1 0 2 1
0 2 1 2
2 0 1 2

 

 

출력 예시 

6

 

 

---

문제 풀이 

 

static class Point {
    int i;
    int j;

    Point(int i,int j){
        this.i=i;
        this.j=j;
}
}

• 도시의 정보(집,피자집의 좌표)를 저장할 사용자 변수 선언 

 

static int n,m;
static int[][] arr;

static List<Point> homes = new ArrayList<>(); // 집의 좌표 저장 
static List<Point> all_pizza= new ArrayList<>(); // 모든 피자집의 좌표 저장 
static Point[] selected; // 선택된 M개의 피자집 좌표 저장 
static int answer = Integer.MAX_VALUE;   // 최종 최소 합

• List를 사용한 이유는 가변 길이 자료형 이기 때문이다.  배열로 선언한다면 도시 정보를 입력 받을때 집은 몇 개인지, 피자집은 몇 개인지 따로 변수를 설정하여 개수를 세어야하기 때문이다. 그래서 정보를 입력 받으면서 동시에 집의 좌표와 피자집의 좌표를 구분하여 저장할 수 있도록 homes와 all_pizza를 List 자료형을 이용하여 저장하였다. 

 

이 문제에서 가장 중요한 것은 결국 도시 정보로 주어진 피자집 중에서 M개를 선택했을때, 어떤 경우에 도시의 피자 배달 거리 값이 최소가 될 수 있는지 구하는 것이다. 

따라서 문제 풀이 순서는 아래와 같다. 

 

1. 도시 정보로 주어진 피자집 중에서 M개를 선택하는 조합을 만든다. 
2. 조합이 선택되면, 각각의 조합에서 도시의 피자 배달 거리를 구한다. 
3. 각각의 조합에서 구한 도시 피자 배달 거리 중 최솟값을 찾는다. 

 

Main 코드 

 

public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st= new StringTokenizer(br.readLine());


    n = Integer.parseInt(st.nextToken()); // 도시의 크기 N*N
    m = Integer.parseInt(st.nextToken()); // 피자집의 개수


    // 배열 정보 입력하기
    arr = new int[n][n];
    selected = new Point[m];

    // 도시 정보 입력하기
    for(int i=0;i<n;i++){
        st = new StringTokenizer(br.readLine());
        for(int j=0;j<n;j++){
            arr[i][j] = Integer.parseInt(st.nextToken());
        }
    }

    // 집과 피자집 위치 로드
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 1) { // 집
                homes.add(new Point(i, j));
            } else if (arr[i][j] == 2) { // 피자집
                all_pizza.add(new Point(i, j));
            }
        }
    }

    // 집의 피자 배달거리를 구하기
    dfs(0,0);
    System.out.println(answer);
}

 

• 먼저 Main 코드에서는 입력 예시와 같이, 도시의 크기와 선택될 피자집의 개수를 입력 받는다. 
• 이후 도시의 정보를 배열에 입력하고, 집과 피자집의 정보를 List 자료형에 따로 저장해둔다. 
• 마지막에 dfs 를 호출하여 계산을 한다. 

 

 

dfs 코드 

static void dfs(int start,int L){
    if(L==m){
        // M개를 다 골랐으면 거리 계산하고 최소값 갱신
        int sum=0;
        for (Point home : homes) {
            int minDist = Integer.MAX_VALUE;
            for (Point p : selected) { // 선택된 M개의 피자집으로 피자 배달거리 구하기
                int dist = Math.abs(home.i - p.i) + Math.abs(home.j - p.j);
                minDist = Math.min(minDist, dist); // 집의 피자 배달거리
            }
            sum+=minDist;// 도시의 피자 배달거리
        }
        answer = Math.min(answer,sum); // M개의 피자집 -> 도시의 최소 배달거리
    }
    for(int i=start;i<all_pizza.size();i++){
        selected[L]=all_pizza.get(i);
        dfs(i + 1, L + 1);
    }
}

 

• 이 코드의 전체적인 틀은 사실 "조합"을 구하는 코드와 동일하다. 
• 피자집의 정보(all_pizza)를 이용하여 조합을 구한다. 이후 M개의 피자집을 모두 선택했다면, 집의 피자 배달 거리를 구하고 도시의 최소 배달 거리를 구한다. 
• 그리고 answer라는 전역 변수를 통해, 각각의 조합의 도시의 최소 배달 거리를 비교하며 최솟값을 저장한다. 

 

 

 

전체 코드 

package 섹션8_DFS_BFS심화;

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

public class Q14_피자배달거리 {
    static int n,m;
    static int[][] arr;

    static List<Point> homes = new ArrayList<>();
    static List<Point> all_pizza= new ArrayList<>(); // 모든 피자집
    static Point[] selected; // 선택된 M개의 피자집
    static int answer = Integer.MAX_VALUE;   // 최종 최소 합

    static void dfs(int start,int depth){
        if(depth==m){
            // M개를 다 골랐으면 거리 계산하고 최소값 갱신
            int sum=0;
            for (Point home : homes) {
                int minDist = Integer.MAX_VALUE;
                for (Point p : selected) { // 선택된 M개의 피자집으로 피자 배달거리 구하기
                    int dist = Math.abs(home.i - p.i) + Math.abs(home.j - p.j);
                    minDist = Math.min(minDist, dist); // 집의 피자 배달거리
                }
                sum+=minDist;// 도시의 피자 배달거리
            }
            answer = Math.min(answer,sum);
        }
        for(int i=start;i<all_pizza.size();i++){
            selected[depth]=all_pizza.get(i);
            dfs(i + 1, depth + 1);
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st= new StringTokenizer(br.readLine());


        n = Integer.parseInt(st.nextToken()); // 도시의 크기 N*N
        m = Integer.parseInt(st.nextToken()); // 피자집의 개수


        // 배열 정보 입력하기
        arr = new int[n][n];
        selected = new Point[m];

        // 도시 정보 입력하기
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 집과 피자집 위치 로드
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] == 1) { // 집
                    homes.add(new Point(i, j));
                } else if (arr[i][j] == 2) { // 피자집
                    all_pizza.add(new Point(i, j));
                }
            }
        }

        // 집의 피자 배달거리를 구하기
        dfs(0,0);
        System.out.println(answer);
    }

    static class Point {
        int i;
        int j;

        Point(int i,int j){
            this.i=i;
            this.j=j;
    }
    }
}