[인프런] 08_14 피자배달거리(DFS) (삼성 SW역량평가 기출문제)

📖  문제

---

문제 설명

• N×N 크기의 도시 지도가 있습니다. 도시 지도는 1 ×1 크기의 격자 칸으로 이루어져 있습니다.
• 각 격자 칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자 칸은 좌표(행 번호, 열 번호)로 표현됩니다.
• 행 번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.
• 도시에는 각 집마다 “피자배달 거리”가 았는데 각 집의 피자배달 거리는 해당 집과 도시의 존재하는
• 피자집들과의 거리 중 최솟값을 해당 집의 “피자배달 거리”라고 한다.
• 집과 피자집의 피자배달 거리는 |x1-x2|+|y1-y2|이다.
• 예를 들어, 도시의 지도가 아래와 같다면

• (1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 |1-2| + |2-3| = 2가 된다.
• 최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있습니다.
• 도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 합니다.
• 시장은 살리고자 하는 피자집 M개를 선택하는 기준으로 도시의 피자배달 거리가 최소가 되는 M개의 피자집을 선택하려고 합니다.
• 도시의 피자 배달 거리는 각 집들의 피자 배달 거리를 합한 것을 말합니다.

입력 설명

• 첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다.
• 둘째 줄부터 도시 정보가 입력된다.

출력 설명

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

문제 풀이

⚠️  주의사항

---

• 최솟값 구하기
• 피자집 총 수를 구한 뒤 M개로 이루어진 조합 구하기

 

✍️  이해

---

/**
 * DFS 코드 풀이
 * TODO
 * 마지막 dis point로 구하는 부분 끝까지 풀지 못해서 다시 풀어봐야함
 *
 * 1. 주어진 입력 받기
 * 2. class Point 이용
 * 3. 2차원 배열 중 house인 곳과 pizza인 곳 나눠서 리스트에 저장
 * 4. if M개 만 골라야하므로 line == M일때 까지 반복
 *  4-1. sum 초기화 후 for-each house로 시작
 *  4-2. 최솟값 구하기 위해 for-each a배열로 전부 찾기
 *   4-2-1. point의 x,y, pizza의 x,y 서로 빼기 (abs 로 절댓값으로 구하기)
 *   4-2-2. 최솟값 구하기 위해서 임의의 함수 만들어서 Math.min(b, 4-2-1)
 *  4-3. 최솟값 구하기 위해서 Math.min(4-2-2, 답)
 * 5. else a배열에 i 저장 후 DFS 호출 (line+1, start+1)
 */

 

✏️  풀이

---

import java.util.ArrayList;
import java.util.Scanner;

class Point{
    public int x, y;

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


public class Main {

    static int N, M, len, minimum = Integer.MAX_VALUE;
    static int[] answer;
    static ArrayList<Point> house, pizza;

    public void DFS(int line, int start) {

        if (line == M) {
            int sum = 0;
            for (Point point : house) {
                int dis = Integer.MAX_VALUE;

                for (int i : answer) {
                    dis = Math.min(dis, Math.abs(point.x - pizza.get(i).x) + Math.abs(point.y - pizza.get(i).y));
                }
                sum += dis;
            }
            minimum = Math.min(minimum, sum);

        } else {
            for (int i = start; i < len; i++) {
                answer[line] = i;
                DFS(line + 1, i + 1);
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        answer = new int[M];

        house = new ArrayList<>();
        pizza = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int temp = sc.nextInt();
                if (temp == 1) house.add(new Point(i, j));
                else if (temp == 2) {
                    pizza.add(new Point(i, j));
                    len++;
                }
            }
        }
        T.DFS(0, 0);
        System.out.println(minimum);
    }
}

---

DFS/BFS 마지막 문제풀이이지만 2시간 이내 풀어보려고 했지만 결국 풀지 못해서 강의를 듣고 이해한 내용을 다시 풀었습니다.
막힌 부분은 dis = ~ 하는 부분부터 어떻게 풀어야 할지 몰라 계속 헤매고 있었어서 결국 정답을 보고 풀었지만 나중에 다시 제 방법대로 풀어서 올려보겠습니다.