피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용)

설명

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개의 피자집이 선택되었을 때 도시의 최소 피자배달거리를 출력한다.

 

예시 입력 1 

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

 

예시 출력 1

6

 

문제 해결

 

이 문제는 각 집마다 피자 배달 거리가 있고 각 집의 피자 배달 거리를 합한 것이 도시의 피자 배달 거리가 되며,

이 때의 최소값을 구하는 문제이다.

 

static int n, m, len, answer = Integer.MAX_VALUE;
static int[] combi;
static ArrayList<Point> hs, pz; // 집과 피자 가게의 좌표를 저장할 리스트들

• n: 도시의 크기 (nxn)
• m: 선택할 피자 가게의 수
• len: 피자 가게의 총 수
• answer: 최소 피자 배달 거리 (초기값을 큰 값으로 설정)
• combi: 선택된 피자 가게의 인덱스를 저장할 배열
• hs: 집의 좌표를 저장할 리스트
• pz: 피자 가게의 좌표를 저장할 리스트

 

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        pz = new ArrayList<>();
        hs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int tmp = in.nextInt(); // 위치 정보를 읽음
                if (tmp == 1) // 집인 경우
                    hs.add(new Point(i, j)); // 집의 좌표를 리스트에 추가
                else if (tmp == 2) // 피자 가게인 경우
                    pz.add(new Point(i, j)); // 피자 가게의 좌표를 리스트에 추가
            }
        }
        len = pz.size(); // 피자 가게의 수
        combi = new int[m]; // m개의 피자 가게를 선택할 배열
        DFS(0, 0); // DFS 호출
        System.out.println(answer); // 결과 출력
    }

• 도시의 크기 n과 선택할 피자 가게의 수 m을 입력받고
• 도시의 각 위치를 입력받아 집과 피자 가게의 좌표를 각각 리스트에 저장한다.
  • 1을 만나면 => 집의 좌표를 ArrayList에 add 시킴
  • 2를 만나면 => 피자집의 좌표를 ArrayList에 add 시킴
• 피자 가게의 총 수를 계산하고, m개의 피자 가게를 선택할 배열을 초기화시켜준다.
• DFS를 사용해 m개의 피자 가게를 선택하고 최소 피자 배달 거리를 계산해 호출한다.
  • m개의 피자집을 선택 => 만약 피자집이 6개가 있고, M이 4라면 6C4 (조합)

조합 하나가 완료되면, 집 하나와의 조합 하나 속 피자집 거리들을 구하고 그 중 최소값이 그 집의 피자배달거리.

 

    public static void DFS(int L, int S) {
        if (L == m) { // m개의 피자 가게를 모두 선택한 경우
            int sum = 0;
            for (Point h : hs) { // 모든 집에 대해
                int dis = Integer.MAX_VALUE;
                for (int i : combi) { // 선택된 피자 가게와의 거리 계산
                    dis = Math.min(dis, Math.abs(h.x - pz.get(i).x) + Math.abs(h.y - pz.get(i).y));
                }
                sum += dis; // 최소 거리의 합
            }
            answer = Math.min(answer, sum); // 최소 배달 거리 갱신
        } else {
            for (int i = S; i < len; i++) { // 피자 가게를 선택
                combi[L] = i;
                DFS(L + 1, i + 1); // 다음 피자 가게 선택
            }
        }
    }
}

• L은 레벨 즉 현재 선택된 피자 가게의 수, S는 선택을 시작할 피자 가게의 인덱스를 의미하고 이를 바e아 DFS를 호출한다.
  • L == m일 때, 즉 m개의 피자 가게를 모두 선택했을 때, 각 집에 대해 선택된 피자 가게와의 최소 거리를 계산하고 그 합을 구한다. 합이 현재까지 구한 최소값보다 작으면 answer를 갱신한다.
  • 그렇지 않으면 피자 가게를 하나씩 선택해 DFS를 재귀적으로 호출한다.

 

최종 코드

 

import java.awt.*;
import java.util.ArrayList;
import java.util.Scanner;

public class P15_피자배달거리 {
    static int n, m, len, answer = Integer.MAX_VALUE;
    static int[] combi;
    static ArrayList<Point> hs, pz; //집, 피자집 좌표들

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        pz = new ArrayList<>();
        hs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int tmp = in.nextInt(); // 각각 위치 정보들 읽음
                if (tmp == 1) //1이면 (즉 집이면)
                    hs.add(new Point(i, j)); //hs 리스트에 좌표 add
                else if (tmp == 2) //2이면 (즉 피자집이면)
                    pz.add(new Point(i, j)); //pz 리스트에 좌표 add
            }
        }
        len = pz.size(); //피자집 개수
        combi = new int[m]; //피자집 개수 중 m개를 뽑아야 하므로
        DFS(0, 0);
        System.out.println(answer);
    }


    public static void DFS(int L, int S) {
        if (L == m) {
//            for(int x : combi) System.out.print(x+" ");
//            System.out.println();
            int sum = 0;
            for (Point h : hs) { //집이 하나 결정되면 (h)
                int dis = Integer.MAX_VALUE;
                for (int i : combi) { //선택된 피자집과 h(집)과의 거리를 모두 구 해 그 중 최소값을 구함
                    dis = Math.min(dis, Math.abs(h.x - pz.get(i).x) + Math.abs(h.y - pz.get(i).y)); //거리값 구하기
                }
                sum += dis; //도시의 피자 배달 거리
            }
            answer = Math.min(answer, sum); //도시의 피자 배달 거리 중 최소
        } else {
            for (int i = S; i < len; i++) {
                combi[L] = i;
                DFS(L + 1, i + 1);
            }
        }
    }
}