[Ch.08 - DFS] 14. 피자 배달 거리 #

14. 피자 배달 거리(삼성 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

---

ArrayList hs[], pz[]

1. m개 선택 후 나머지 pop
2. DFS 이용, 6C4 =15가지
3. 집들마다, for(선택된 피자집) 루프
   1. dis배열에서 그 중 최솟값 +=sum
   2. 선택된 피자집을 변경 -> 6C4 중 최솟값
      = 도시의 최소 피자 배달 거리

 

---

조합 경우의 수 출력

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;
	}
}
//피자 배달 거리
//각 집들의 최소 배달 거리 = 피자배달거리
//각 집들의 최소 배달 거리의 합 = 도시의 피자 배달거리
//M개의 피자집을 살리는 도시의 피자 배달거리의 최소값
class Main {
	static int n,m, len, answer=Integer.MAX_VALUE;
	static int[] combi;
	static ArrayList<Point> pz,hs;
	public void DFS(int L, int s) {
		if(L==m) {
			//조합이 완성될 경우 각 집의 피자배달거리 구하고 합해서 도시의 최소 피자배달거리 구함
			for(int x : combi) {
				System.out.println(x+" ");
				//조합의 경우의 수를 출력 -> 15개
			}
			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++) {
				//조합의 경우의 수 6C4 -> 조합을 구하는 반복문 외우기
				combi[L]=i;
				//0 ~ 5 -> M개를 뽑는다.
				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();
		pz=new ArrayList<>();
		hs=new ArrayList<>();
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				int tmp=kb.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];
		T.DFS(0, 0);
		System.out.println(answer);
	}
  
}

 

0 1 2 3 
0 1 2 4 
0 1 2 5 
0 1 3 4 
0 1 3 5 
0 1 4 5 
0 2 3 4 
0 2 3 5 
0 2 4 5 
0 3 4 5 
1 2 3 4 
1 2 3 5 
1 2 4 5 
1 3 4 5 
2 3 4 5

 

#조합의 경우에서, 피자배달거리 구하고, 도시의 피자배달거리 찾기

if(L==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);
    //도시의 최소 피자배달거리
}

 

 

(1) 3개 선택할 피자집 번호

-> 조합의 경우의 수

(2) 선택한 피자집들 중 가장 짧은 최소거리만 선택해 더하기

(3) 각 집들의 최소 피자 배달거리

(4) 그중 answer에 가장 작은 각 집들의 최소 배달 거리를 선택해 더한다.

 else{
      //조합을 구하는 반복문
      //: s=0부터 len까지 [피자집 개수만큼] -> combi배열은 남을 피자집 개수만큼
      for(int i=s;i<len;i++){
        combi[L]=i;
        DFS(L+1, i+1);
      }
    }

import java.util.*;
class Pos{
  public int x,y;
  Pos(int x, int y){
    this.x=x;
    this.y=y;
  }
  //pz.size() 중 m개 선택
  //도시의 피자배달 거리 : 각 집들의 피자배달거리를 합한것
  //각 집들의 피자배달거리 : [피자집 x위치 -집 x위치] + [피자집 y위치 -집 y위치]
}
public class Main {
  static int n,m, len, answer=Integer.MAX_VALUE;
  static int[][] arr;
  static int[] combi;
  static ArrayList<Pos> pz = new ArrayList<>();
  static ArrayList<Pos> hs = new ArrayList<>();
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    n = in.nextInt();
    m = in.nextInt();
    arr = new int[n][n];
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        arr[i][j]=in.nextInt();
        if(arr[i][j]==1) hs.add(new Pos(i,j));
        if(arr[i][j]==2) pz.add(new Pos(i,j));
      }
    }
    //조합의 경우의 수 :피자집 개수와, 남을 피자집 길이 배열
    len=pz.size();
    combi=new int[m];
    DFS(0,0);
    System.out.println(answer);
  }
  //6C4
  static void DFS(int L, int s){
    //중단 조건 :L이 남을 피자집 개수만큼 된다면
    if(L==m){
      //각 집의 피자 배달거리 구하기
      
      int sum=0;
      for(Pos h : hs){
        int dis=Integer.MAX_VALUE;
        //combi 배열에 3개를 선택한 피자집 번호가 정해져있다.
        for(int i : combi){
          //각 집마다 최소 피자배달 거리를 구하기 위해 -> 3개의 피자집들의 조합 중에 가장 짧은 거리 구한다.
          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{
      //조합을 구하는 반복문
      //: s=0부터 len까지 [피자집 개수만큼] -> combi배열은 남을 피자집 개수만큼
      //남아야할 피자집 개수 : 4 * 4 :L이 0부터 4까지/// 16가지인데 마지막은 여기 안옴 -1가지
      for(int i=s;i<len;i++){
        combi[L]=i;
        DFS(L+1, i+1);
      }
    }
  }
}