[Java] 백준 15686.치킨 배달

➡️문제 링크

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

 

 

💡아이디어

완-탐 / 조합

주어진 치킨집 중 M개를 선택해야한다는 조건을 보고

한 번에 완벽한 M개를 고르는 방법이 있는가? -> X

그렇다면 모든 치킨집 중 임의로 M개를 뽑아 최소 치킨 거리를 뽐내는지 확인해야겠다 싶어

조합을 만들어 탐색했다

 

 

✏️문제 풀이

1. 완탐,구현 - 성공

1. 치킨집과 집의 좌표를 각각 저장

2. 전체 치킨집 중 M개를 뽑아 해당 치킨집과 치킨 거리를 구해 비교한다.

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

public class Main {
	static int N,M;
	static int [][] map;
	static List<int []> chickenList = new ArrayList<>();
	static List<int []> homeList = new ArrayList<>();
	static int result = Integer.MAX_VALUE;
	static int [] arr;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][N];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 2) chickenList.add(new int[] {i, j});	// 치킨집 위치
				else if(map[i][j] == 1) homeList.add(new int[] {i, j});	// 집 위치
			}
		}
		
		if(M == chickenList.size()) {
			solve(chickenList);
		}else {
			arr = new int[M];
			recursion(0, 0);
		}
		
		// 출력
		System.out.println(result);
	}
	
	static void recursion(int depth, int start) {
		if(depth == M) {
			List<int []> tmp = new ArrayList<>();
			for(int idx : arr) {
				tmp.add(chickenList.get(idx));
			}
			solve(tmp);
			
			return;
		}
		
		for(int i = start; i < chickenList.size(); i++) {
			arr[depth] = i;
			recursion(depth+1, i+1);
		}
	}
	
	static void solve(List<int []> list) {
		int totalDist = 0;

		for(int i = 0; i < homeList.size(); i++) {
			int curMinDist = Integer.MAX_VALUE;
			int r1 = homeList.get(i)[0];
			int c1 = homeList.get(i)[1];
			
			for(int j = 0; j < list.size(); j++) {
				int r2 = list.get(j)[0];
				int c2 = list.get(j)[1];
				int dist = Math.abs(r1-r2) + Math.abs(c1-c2);
				curMinDist = Math.min(curMinDist, dist);	// 치킨집 리스트 중 치킨 거리 가장 작은 것 추출
			}
			totalDist+= curMinDist;

		}

		result = Math.min(result, totalDist);
	}

}

 

 

2.  완탐, 구현- 성공

다른 사람들의 풀이를 살펴 보니 미리 집과 각 치킨집별 거리를 구한 뒤, 조합을 구현했다

그리고 문제에서는 각 집과 치킨집의 좌표만 필요하기에, 2차원 배열 map은 만들 필요가 없었다

2차원 배열만 보면 무조건 저장하는 습관이 있는데

문제를 잘 읽어 봐야겠다 

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

public class Main {
	static int N,M;
	static List<int []> chickenList = new ArrayList<>();
	static List<int []> homeList = new ArrayList<>();
	static int [][] dist;
	static int [] pick;
	static int minDist = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		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 == 2) chickenList.add(new int[] {i, j});	// 치킨집 위치
				else if(num == 1) homeList.add(new int[] {i, j});	// 집 위치
			}
		}
		
		// 각 집마다 - 치킨집별  치킨 거리 구하기
		dist = new int[homeList.size()][chickenList.size()];
		
		for(int i = 0; i < homeList.size(); i++) {
			int r1 = homeList.get(i)[0];
			int c1 = homeList.get(i)[1];
			
			for(int j = 0; j < chickenList.size(); j++) {
				int r2 = chickenList.get(j)[0];
				int c2 = chickenList.get(j)[1];
				dist[i][j] = Math.abs(r1-r2) + Math.abs(c1-c2);
			}
		}
		
		// M개 치킨집 뽑기
		pick = new int[chickenList.size()];
		recursion(0, 0);
		
		// 출력
		System.out.println(minDist);
	}
	
	static void recursion(int depth, int start) {
		if(depth == M) {
			minDist = Math.min(minDist, calDist());
			
			return;
		}
		
		for(int i = start; i < chickenList.size(); i++) {
			pick[depth] = i;
			recursion(depth+1, i+1);
		}
	}
	
	static int calDist() {
		int totalDist = 0;

		for(int i = 0; i < homeList.size(); i++) {
			int curMinDist = Integer.MAX_VALUE;
			
			for(int j = 0; j < M; j++) {
				curMinDist = Math.min(curMinDist, dist[i][pick[j]]);
			}
			totalDist += curMinDist;
		}
		
		return totalDist;
	}

}