[PS] 인프런 강의 - DFS 12. 피자 배달 거리(삼성 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개의 피자집이 선택되었을 때 도시의 최소 피자배달거리를 출력한다.

 

▣ 입력예제 1
4 4
0 1 2 0
1 0 2 1
0 2 1 2
2 0 1 2

 

▣ 출력예제 1
6

 

풀이

 

모든 집에서 피자집 m개와의 최소거리를 구해야하는데 다소 헷갈릴 수 있다..

 

*도시의 피자배달거리 = 각 집의 피자배달거리의 합 = 각 집에서 피자집 m개 중 가장 가까운 거리의 합

 

따라서 피자집 m개가 선택됐을 때,
모든 집을 순회하면서  피자배달거리(피자 집과의 거리 중 최소값)를 구한 값의 합계를 구했을 때

그 합계가 최소인 경우의 수를 구하는 문제이다. 즉 조합 구하기 문제의 응용버전이라고 할 수 있다.

 

 

combi[0] = 0;
DFS(1,1);

combi[1] = 1;
DFS(2,2);

combi[2] = 2;
DFS(3 3);

combi[3] = 3;
DFS(4 4);  --> if(L==m) 로직 수행 : (인덱스)0,1,2,3 피자집일 경우 도시의 피자배달거리 최소값 구하고 다음 조합으로 넘어간다

 

코드

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

public class Main {
	static int n, m, len;
	static ArrayList<Point> hs, pz;
	static int[] combi; //pz에서 m개 뽑아서 여기 넣음
	static int answer = Integer.MAX_VALUE; //최소값 구함
	
	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) { //피자집 m개 순회
					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 {
			//combi : 피자집 m개 뽑기
			for(int i=s; i<len; i++) { //피자집 순회
				combi[L] = i; //ArrayList의 인덱스 번호
				DFS(L+1, i+1);
			}
		}
	}
 
	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        n = in.nextInt();
        m = in.nextInt();
        
        //1은 집, 2는 피자집
        hs = new ArrayList<>();
        pz = 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]; //len C m
        DFS(0, 0);
        System.out.println(answer);
        
    }
}