Java - [백준]15686- 치킨 배달

출처

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

문제

치킨집을 M개만 남기고 나머지는 폐업하려고 한다. 이때, 도시의 치킨거리가 가장 적도록 폐업하는 방법을 구하는 문제입니다.

접근 방법

처음에는 치킨집의 인덱스를 가지고 조합을 생성하여 계산하거나 단순 완전탐색으로 구현하려고 하였습니다. 하지만 알고보니 이렇게 비효율적이고 어렵게 하기 보다는, 백트래킹을 이용하면 간단하게 해결할 수 있었습니다.

완전탐색으로 풀 수 있는 문제 중 순열이나 조합을 구하는 문제는 백트래킹으로 풀 수 있기 때문입니다.

풀이

1. 집과 치킨집의 좌표를 Node 자료구조를 정의/이용하여 List에 넣고
2. 치킨집의 폐업 여부를 알려주는 boolean 배열을 선언합니다.
3. dfs알고리즘을 통해 정답을 구합니다.
   i. 오픈한 치킨집의 갯수인 count가 M과 같다면
   ii. 현재의 경우에서 모든 집에 대해 최단 치킨거리를 구하고
   iii. 현재 구한 최단거리와 비교하여 min함수를 이용하여 최솟값을 저장합니다.

아래 코드를 보면 이해가 더 수월할 것입니다.

코드

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

public class Main {
	static int N, M;
	static int[][] map;
	static List<Node> house;
	static List<Node> chicken;
	static int answer;
	static boolean[] remaining;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		house = new ArrayList<>();
		chicken = new ArrayList<>();
		map = new int[N][N];

        // map과 치킨집, 집의 리스트를 저장
        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) {
					house.add(new Node(i, j));
				}
				if (map[i][j] == 2) {
					chicken.add(new Node(i, j));
				}
			}
        }

		answer = Integer.MAX_VALUE;
		remaining = new boolean[chicken.size()];
		dfs(0, 0);
		bw.write(answer + "\n");

        br.close();
        bw.flush();
        bw.close();
    }

    // dfs를 이용하여 탐색 진행
	public static void dfs(int start, int count){
		if (count == M) {
			int result = 0;

			for (int i = 0; i < house.size(); i++) {
				int tmp = Integer.MAX_VALUE;

				for (int j = 0; j < chicken.size(); j++) {
					if (remaining[j]) {
						int distance = Math.abs(house.get(i).x - chicken.get(j).x) 
						+ Math.abs(house.get(i).y - chicken.get(j).y);
						tmp = Math.min(tmp, distance);
					}
				}
				result += tmp;
			}
			answer = Math.min(answer, result);
			return ;
		}


        // 모든 치킨집에 대해 backtracking
		for (int i = start; i < chicken.size(); i++) {
			remaining[i] = true;
			dfs(i + 1, count + 1);
			remaining[i] = false;
		}
	}

}

class Node{
	int x;
	int y;

	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}