피자 배달 거리 (DFS)

in Algorithm / Java coding test on Algorithm, Java, Coding test, 알고리즘, 자바, 코딩 테스트

문제

설명

N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다.

각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자칸은 좌표(행번호, 열 번호)로 표현됩니다.

행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.

도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재하는

피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다.

집과 피자집의 피자배달거리는x1-x2+y1-y2이다.

예를 들어, 도시의 지도가 아래와 같다면

https://cote.inflearn.com/public/upload/15230e4e41.jpg

(1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는1-2+2-3= 2가 된다.

최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있습니다.

도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 합니다.

시장은 살리고자 하는 피자집 M개를 선택하는 기준으로 도시의 피자배달거리가 최소가 되는 M개의 피자집을 선택하려고 합니다.

도시의 피자 배달 거리는 각 집들의 피자 배달 거리를 합한 것을 말합니다.

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다.

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

출력

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

예시 입력 1

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

예시 출력 1

6

해결방법

  • 조합, N개 중에 M개 뽑는 경우의 수
public void DFS(int L, int s) {
        // 4개를 뽑았다?
        if (L == m) {
            for (int x : combi) {
                System.out.print(x + " ");
            }
            System.out.println();
        } else {
            // 뽑지 않았다.
            for (int i = s; i <= len; i++) {
                // 피자집 개수 중에 뽑아야 함.
                combi[L] = i;
                DFS(L + 1, i + 1);

            }
        }
    }
  • 조합 구조는 알고 있는게 낫다. 조합을 뽑는 것이라는 걸 인지하면 구조를 그려놓고 로직을 생각하는게 편하다.

코드

import java.util.*;

class Point {
    public int x, y;

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

class Main {
    static int n, m, len;
    static int[] combi;

    static int min = Integer.MAX_VALUE;
    static int[][] city;

    static ArrayList<Point> house = new ArrayList<>();
    static ArrayList<Point> pizza = new ArrayList<>();

    public void DFS(int L, int s) {
        // 4개를 뽑았다?
        if (L == m) {
            // 조합이 완성 될 때 마다, 각 거리를 계산하여 도시의 피자 배달 거리를 구한다.
            int sum = 0;
            for (Point h : house) {
                int dis = Integer.MAX_VALUE;
                for (int i : combi) {
                    // 해당 집과 뽑은 피자집과의 거리 중 최소값 = 도시 피자 배달 거리
                    dis = Math.min(dis, Math.abs(h.x - pizza.get(i).x) + Math.abs(h.y - pizza.get(i).y));
                }
                // 모든 집에 대한 도시 피자 배달 거리 더하여 값을 구한다.
                sum += dis;
            }
            // 최소 값 구하는 거니까 .. 비교
            min = Math.min(sum, min);
        } else {
            // 뽑지 않았다.
            for (int i = s; i < len; i++) {
                // 피자집 개수 중에 뽑아야 함.
                combi[L] = i;
                DFS(L + 1, i + 1);

            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int temp = kb.nextInt();
                if (temp == 1) house.add(new Point(i, j));
                else if (temp == 2) pizza.add(new Point(i, j));
            }
        }
        len = pizza.size();
        combi = new int[m];
        T.DFS(0, 0);
        System.out.println(min);
    }
}

© 2024. Chiptune93 All rights reserved.