문제

백준 15686 치킨 배달 문제 보러가기



문제점 해결

문제를 보자마자 순열로 풀어야한다고 생각했는데 시간계산을 했을 때 주어진 시간을 넘겨서 다른 방법을 찾아보려 했지만 순열로 푸는 문제가 맞았다. 치킨집의 최대 개수는 13개이고 M의 값고 최대 13이기 때문에 순열 계산을 하면 최악의 경우 13!이 나오기 때문에 1초라는 시간을 넘기고도 남는다.. 그러나 실제로 제출한 결과 통과되었고 시간도 200ms를 넘지 않았다.. 시간복잡도를 계산했을 때는 분명히 실패여야 하는데 언어에 따라 추가시간이 있는것인지.. M이 10개 이상인 테케가 없는것인지.. 도통 모르겠다 ㅠㅠ



풀이

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

public class Main {
	static int N, M, answer;
	static int[][] map;
	static ArrayList<Point> homeList, chickenList;

	static class Point {
		int i, j;

		public Point(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}

	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];
		homeList = new ArrayList<>();
		chickenList = new ArrayList<>();

		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] == 1)
					homeList.add(new Point(i, j));
				else if (map[i][j] == 2)
					chickenList.add(new Point(i, j));
			}
		}

		int[][] dist = calculateDistance();
		if (M == chickenList.size()) {
			int sum = 0;
			for (int i = 0; i < homeList.size(); i++) {
				int min = Integer.MAX_VALUE;
				for (int j = 0; j < chickenList.size(); j++) {
					min = Math.min(dist[i][j], min);
				}

				sum += min;
			}
			System.out.println(sum);
			return;
		}

		answer = Integer.MAX_VALUE;
		permutation(dist, new boolean[chickenList.size()], 0, 0);
		System.out.println(answer);
	}

	public static void permutation(int[][] dist, boolean[] used, int count, int index) {
		if (count == M) {
			int[] result = new int[homeList.size()];
			Arrays.fill(result, Integer.MAX_VALUE);
			
			for (int j = 0; j < used.length; j++) {
				if(used[j]) {
					for (int i = 0; i < homeList.size(); i++) {
						result[i] = Math.min(result[i], dist[i][j]);
					}
				}
			}
			
			int sum = 0;
			for (int i = 0; i < result.length; i++) {
				sum += result[i];
				if(sum > answer) return;
			}
			
			answer = Math.min(answer, sum);
			return;
		}

		for (int i = index; i < used.length; i++) {
			if (!used[i]) {
				used[i] = true;
				permutation(dist, used, count + 1, i + 1);
				used[i] = false;
			}
		}
	}

	public static int[][] calculateDistance() {
		int[][] dist = new int[homeList.size()][chickenList.size()];

		for (int i = 0; i < homeList.size(); i++) {
			Point home = homeList.get(i);

			for (int j = 0; j < chickenList.size(); j++) {
				Point chicken = chickenList.get(j);

				dist[i][j] = Math.abs(chicken.i - home.i) + Math.abs(chicken.j - home.j);
			}
		}

		return dist;
	}
}