[백준] BOJ 15686 치킨 배달(JAVA/시간초과 해결)

 

모든 경우의 수를 확인해 보는 문제이다.

 

 

 

 

해당 조건을 보며 치킨 집 중에서 M개에 대해 나올 수 있는 경우의 수를 전부 확인하여, 도시의 치킨 거리를 구해야겠다고 생각했다.

 

 

처음에는 방문체크 여부를 확인하여 해당 치킨 집을 방문하지 않았다면 방문하는 식으로 진행했다.

 

	/*
	 * M개의 치킨집을 선택할 수 있는 경우의 수를 전부 구함
	 * */
	static void choice(int cnt, int[] output, boolean[] visited, int now) {
		//M개의 치킨 집 전부 구함
		if (cnt >= M) {
			getDistance(output);
			return;
		}

		//다음 치킨 집 선택
		for (int i = now; i < chickenList.size(); i++) {
			if (!visited[i]) {
				visited[i] = true;
				output[cnt] = i;
				choice(cnt + 1, output, visited, now+1);
				visited[i] = false;
			}
		}
	}

 

 

하지만 이 경우에는 시간 초과가 발생한다.

 

 

 

 

해당 문제에 대해 생각해보니 위의 코드 즉, 조합으로 진행하면 (1,2), (2,1)에 대해 다른 경우로 판단하는데, 치킨의 집의 좌표 List 중에서 선택하는 것이므로 (1,2)나 (2,1)는 같은 경우의 수로 판단하도록 진행하였다.

 

 

 

 

따라서, 다음과 같이 인덱스를 now부터 시작하도록 진행하였다. 이렇게 하면 (1,2)와 (2,1) 두 가지 경우의 수를 카운트하는 게 아니라 (1,2)에 대해서만 경우의 수를 구하게 된다.

 

그리고 주의할 점이 다음 치킨 집 선택할때 i+1을 넘겨주어야 한다!!!!

	/*
	 * M개의 치킨집을 선택할 수 있는 경우의 수를 전부 구함
	 * */
	static void choice(int cnt, int[] output, int now) {
		//M개의 치킨 집 전부 구함
		if (cnt >= M) {
			getDistance(output);
			return;
		}

		//다음 치킨 집 선택
		for (int i = now; i < chickenList.size(); i++) {
			output[cnt] = i;
			choice(cnt + 1, output, i + 1);
		}
	}

 

 

 

 

---

구현

public class Main_15686 {
	static int N;
	static int M;
	static int result;

	static LinkedList<int[]> chickenList = new LinkedList<>();
	static LinkedList<int[]> homeList = new LinkedList<>();

	static int[][] maps;

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


		choice(0, new int[M], 0);

		System.out.println(result);
	}

	/*
	 * M개의 치킨집을 선택할 수 있는 경우의 수를 전부 구함
	 * */
	static void choice(int cnt, int[] output, int now) {
		//M개의 치킨 집 전부 구함
		if (cnt >= M) {
			getDistance(output);
			return;
		}

		//다음 치킨 집 선택
		for (int i = now; i < chickenList.size(); i++) {
			output[cnt] = i;
			choice(cnt + 1, output, i + 1);
		}
	}

	/*
	 * 선택한 치킨 집에 대해 도시의 치킨 거리 계산
	 * */
	static void getDistance(int[] output) {
		int sum = 0;

		for (int i = 0; i < homeList.size(); i++) {
			int min = Integer.MAX_VALUE;
			int[] home = homeList.get(i);
			int homeX = home[0], homeY = home[1];
			for (int j = 0; j < output.length; j++) {
				int[] tmp = chickenList.get(output[j]);
				int chickenX = tmp[0], chickenY = tmp[1];
				min = Math.min(min, Math.abs(homeX - chickenX) + Math.abs(homeY - chickenY));
			}
			sum += min;
		}

		result = Math.min(result, sum);

	}

}