[백준] 15686. 치킨배달 - 골드5

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

15686번: 치킨 배달

 

문제 요약

N * N 크기의 도시가 있다. 도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 골라야 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

치킨 거리란 집과 가장 강까운 치킨집 사이의 거리이다. 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

 

문제 해결 아이디어

완전 탐색으로 해결했다. 입력받을 때 치킨집의 개수를 세어 그 중 M개를 뽑고, 다 뽑힐 때마다 치킨 거리를 계산하여 최솟값을 비교해 주었다.

 

완성된 코드

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

public class Main {
	/*
	 * 168ms
	 */
	static int N, M, min;
	static int[][] map, chicken, answer;
	static boolean[] visited;

	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());

		map = new int[N][N];
		chicken = new int[13][2]; // 최대 13개

		int c = 0;
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0, index = 0; j < N; j++, index += 2) {
				map[i][j] = str.charAt(index) - '0';
				if (map[i][j] == 2) {
					chicken[c][0] = i;
					chicken[c][1] = j;
					c++;
				}
			}
		}

		visited = new boolean[c];
		answer = new int[M][2];
		min = Integer.MAX_VALUE;
		// 치킨집 중 M개를 뽑고
		// 그에 해당하는 최소값을 갱신...?
		pick(0, 0);
		System.out.println(min);
	} // end of main

	private static void pick(int start, int cnt) {
		if (cnt == M) {
			int temp = 0, dis = 0, sum = 0;

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					temp = Integer.MAX_VALUE;
					if (map[i][j] == 1) {
						for (int k = 0; k < answer.length; k++) {
							dis = Math.abs(answer[k][0] - i) + Math.abs(answer[k][1] - j);
							temp = Math.min(temp, dis);
						}
						sum += temp;
					}
				}
			}
			min = Math.min(sum, min);
			return;
		}

		for (int i = start; i < visited.length; i++) {
			if (visited[i])
				continue;
			answer[cnt][0] = chicken[i][0];
			answer[cnt][1] = chicken[i][1];
			visited[i] = true;
			pick(i, cnt + 1);
			visited[i] = false;
		}
	}

} // end of class