[백준/브루트포스, 구현] 15686: 치킨 배달 - 자바

문제

---

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

15686번: 치킨 배달

 

풀이

---

도시의 지도 데이터를 입력받으면서 치킨집 좌표와 집 좌표를 list자료형에 입력하였다.

문제에서는 치킨집 개수 M개 일 때 치킨집 거리와 집 거리의 합들이 최소가 될 때 그 길이를 구하는 것을 요구한다.

 

처음에 치킨집의 좌표를 조합으로 출력하여 각 치킨집이 해당 위치에 있을 때 BFS탐색을 통해 집까지의 거리를 구하려고 했다. 그러나 이렇게 하면 너무 오래 걸릴 뿐더러 입력값으로 집의 좌표와 치킨집의 좌표가 입력되므로 두 사이의 좌표 차이가 거리이다. 

따라서 BFS를 쓰지 않아도 되는 문제이다.

경로 탐색에서는 그래프 탐색 알고리즘을 많이 활용하는데 문제에서 주어진 요건을 잘 읽어보면 굳이 쓰지 않아도 되는 알고리즘을 사용할 필요가 없다는 것을 알았다.

 

문제를 해결한 흐름은 다음과 같다.

1. 치킨집과 집의 좌표를 list형에 저장한다.
2. 전체 치킨집 N개에서 폐업시키지 않을 치킨집 M개의 조합 즉, N_C_M을구한다.
3. 조합 경우의 수 하나 당 그 결과의 좌표(치킨집 좌표)와 집 좌표의 차이를 구함.
4. N_C_M의 경우의 수 만큼 3번 과정을 반복하여 가장 작은 거리값을 구함.

 

본인은 다음과 같이 해결하였다.

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

public class BOJ_15686 {
	static StringTokenizer st;
	static int N, M;
	static int ans = Integer.MAX_VALUE;
	static int[][] chickenGetList;
	static List<int[]> house;
	static List<int[]> chicken;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st= new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		chicken = new LinkedList<>();
		house = new LinkedList<>();
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < N; j++) {
				int temp = Integer.parseInt(st.nextToken());
				
				if(temp == 2) {
					int[] temp2 = {i, j};
					chicken.add(temp2);
				} else if (temp == 1) {
					int[] temp1 = {i,j};
					house.add(temp1);
				}
			}
		}
		chickenGetList = new int[chicken.size()][2];
		comb(0,0);
		System.out.println(ans);
	}
	
	public static void comb(int cnt, int start) {
		if (cnt == M) {
			diffDistance();
			return;
		}

		for (int i = start; i < chicken.size(); i++) {
			chickenGetList[cnt][0] = chicken.get(i)[0];
			chickenGetList[cnt][1] = chicken.get(i)[1];
			comb(cnt + 1, i + 1);
		}
		
	}
	
	public static void diffDistance() {
		int minDistance = 0;

		for (int i = 0; i < house.size(); i++) {
			int min = Integer.MAX_VALUE;
			for (int j = 0; j < M; j++)	{
				min = Math.min(min, Math.abs(chickenGetList[j][0] - house.get(i)[0]) + 
						            Math.abs(chickenGetList[j][1] - house.get(i)[1]));
			}
			minDistance += min;
		}
		ans = Math.min(ans, minDistance);
		return;
	}
}

 

다른 풀이(비트마스크)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_15686 {
	static int[][] distance;
	static int minChickenDistance;
	static int houseNum;
	static int storeNum;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		List<House> houseList = new ArrayList<>();
		List<House> chickenStoreList = new ArrayList<>();
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				int value = Integer.parseInt(st.nextToken());
				if(value == 1)
					houseList.add(new House(i,j));
				else if(value == 2)
					chickenStoreList.add(new House(i,j));
			}
		}
		
		houseNum = houseList.size();
		storeNum = chickenStoreList.size();

		distance = new int[houseNum][storeNum];
		for(int i = 0; i < houseNum; i++) {
			House house = houseList.get(i);
			for(int j = 0; j < storeNum; j++) {
				House store = chickenStoreList.get(j);
				distance[i][j] = Math.abs(house.x - store.x) + Math.abs(house.y - store.y);
			}
		}

		minChickenDistance = Integer.MAX_VALUE;
		comb(0,0, M, 0);
		System.out.println(minChickenDistance);
	}
	
	private static void comb(int start, int depth, int target, int flag) {
		if(depth == target) {
			int sum = 0;
			for(int i = 0; i < houseNum; i++) {
				int min = Integer.MAX_VALUE;
				for(int j = 0; j < storeNum; j++) {
					if((flag & 1<<j) != 0) {
						min = Math.min(min, distance[i][j]);
					}
				}
				sum += min;
			}
			minChickenDistance = Math.min(minChickenDistance, sum);
			return;
		}
		for(int i = start; i < storeNum; i++) {
			if((flag & 1<<i) != 0)	continue;
			comb(i+1, depth + 1, target, flag | 1 << i);
		}
	}

	static class House{
		int x;
		int y;
		
		public House(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}