[백준 15686] 치킨 배달

📍 문제

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

 

📍 문제 풀이

 

풀이과정은 아래와 같다.

1. 집과 치킨집의 좌표를 각각 리스트에 저장한다.

2. 가능한 치킨집의 조합을 모두 구한다.

3. 조합별 집과의 치킨 거리를 구한다. 이를 통해 도시 전체의 치킨 거리를 구한다.

4. 도시 전체 치킨 거리가 더 작다면 값 갱신

 

이때 가능한 치킨집의 조합은 opened 배열로 확인했다. 

값이 true라면 치킨집이 열려있고, false면 닫혀있다고 생각하고 풀이를 진행했다. 

 

📍전체코드

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

public class boj_15686 {
	static int[][] maps;
	static int n, m;
	static List<int[]> houses;
	static List<int[]> chickens;
	static boolean[] opened;
	static int result;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		maps = new int[n][n];
		houses = new ArrayList<>();
		chickens = new ArrayList<>();
		result = Integer.MAX_VALUE;

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < n; j++) {
				maps[i][j] = Integer.parseInt(st.nextToken());

				if(maps[i][j] == 1){	// 집
					houses.add(new int[]{i, j});
				} else if (maps[i][j] == 2) {	// 치킨집
					chickens.add(new int[]{i, j});
				}
			}
		}

		opened = new boolean[chickens.size()];

		dfs(0, 0);
		System.out.println(result);

	}

	private static void dfs(int depth, int idx) {
		if (depth == m) {
			int total_length = 0;

			// 조합별 치킨거리 구하기
			for (int i = 0; i < houses.size(); i++) {
				int chicken_length = Integer.MAX_VALUE;
				for (int j = 0; j < chickens.size(); j++) {
					if (opened[j]) {	// 치킨집을 열었다면
						int dist = Math.abs(houses.get(i)[0] - chickens.get(j)[0]) + Math.abs(houses.get(i)[1] - chickens.get(j)[1]);
						chicken_length = Math.min(chicken_length, dist);
					}
				}
				total_length += chicken_length;
			}
			result = Math.min(result, total_length);
			return;
		}


		// 가능한 조합 구하기
		for (int i = idx; i < chickens.size(); i++) {
			opened[i] = true;
			dfs(depth + 1, i + 1);
			opened[i] = false;
		}
	}

}