[백준] 15686번 치킨배달 ( java)

문제

입력

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

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

---

풀이

문제에서 가장 필요한 값은 가정집과 치킨집의 주소(i,j)이기 때문에 전체를 이차원배열로 저장하여 사용하려면 많은 번거로움이 있다.

(치킨집의 수가 유동적이기 때문에!)

따라서 이차원배열을 만들지 않고 home, chic이라는 리스트를 만들어서 사용하였다.

각각의 배열대신 리스트를 사용한 이유는 가정집이랑 치킨집 수가 정해져 있지 않으니까!

 

문제만보면 고려해야할 점이 굉장히 많은데, 핵심은 치킨집을 선택하는 것! -> 조합!

일반적인 조합코드를 작성하였고 기저조건 내에서

가정집-치킨집 사이의 거리

도시의 치킨거리

치킨집 조합들 중 최소 치킨거리 를 계산.

 

이때, 주의할 점.

리스트는 add시 배열처럼 해당 인덱스의 값을 덮어씌우는 것이 아니기 때문에,

만약 현재 remChic.size == cnt라면, 즉 배열로 따졌을 때 같은 인덱스에 다른 값을 넣는 경우라면

add가 아닌 set으로 값을 replace해주어야 한다.

---

코드

import java.io.*;
import java.util.*;

public class Main{
	//가정집과 치킨집의 수가 정해져있지 않기 때문에 배열대신 List사용
	static List<int[]> home;				//가정집 주소를 저장할 리스트
	static List<int[]> chic;				//치킨집 주소를 저장할 리스트
	static List<int[]> remChic;				//선택한 치킨집 주소를 저장할 리스트
	static int chic_dis;					//결과값: 최단치킨거리
	static int n,m;							//도시 너비, 남겨야하는 치킨집 수
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		home = new ArrayList<int[]>();
		chic = new ArrayList<int[]>();
		remChic = new ArrayList<int[]>();
		for(int i =0 ; i < n ; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j =0 ; j < n ; j++) {
				int  num = Integer.parseInt(st.nextToken());
				if(num == 1) home.add(new int[] {i,j});				//가정집 주소(i,j)를 배열형태로 리스트에 저장
				else if(num == 2) chic.add(new int[] {i, j});		//치킨집 주소(i,j)를 배열형태로 리스트에 저장
			}
		}
		chic_dis = Integer.MAX_VALUE;								//최솟값 비교를 위해 결과값의 초기값을 MAX INTEGER로 설정
		chicDis(0,0);
		System.out.println(chic_dis);
	}
	
	public static void chicDis(int cnt, int start) {
		if(cnt == m) {							//기저조건: 현재 선택한 치킨집 갯수(cnt)가 남겨야하는 치킨집 개수(m)일때
			int chic_dis_tmp = 0;				//선택한 치킨집 개수에 따른 치킨거리를 저장할 변수
			for(int i =0 ; i < home.size() ; i++) {	
				int dis = Integer.MAX_VALUE;	//가정집과 치킨집 사이의 거리를 저장할 변수 	
				for(int j = 0 ; j < remChic.size() ; j++) {			//선택된 치킨집들과의 치킨거리를 계산해 최솟값 찾기
					dis = Math.min(dis, Math.abs(home.get(i)[0]-remChic.get(j)[0])+ Math.abs(home.get(i)[1]-remChic.get(j)[1]));
				}
				chic_dis_tmp += dis;			//치킨거리 계산
			}
			chic_dis = Math.min(chic_dis, chic_dis_tmp);		//지금까지의 조합 중, 가장 작은 치킨거리 값 찾기
			return;
		}
		for(int i = start; i < chic.size() ; i++) {				//치킨집 조합 코드
			if(remChic.size() == cnt) remChic.add(chic.get(i));			
			else remChic.set(cnt, chic.get(i));
			chicDis(cnt+1, i+1);
		}
	}
}