백준 10819번
https://www.acmicpc.net/problem/15686

문제

---

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

생각하기

---

동작

		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				int num = Integer.parseInt(st.nextToken());

				if(num == 2) {
					chickenList.add(new Node(i, j, false));
				}
				else if(num == 1) {
					houseList.add(new Node(i, j, false));
				}
				arr[i][j] = num;
			}
		}

배열arr을 생성하면서, 집의 위치와 치킨 집의 위치의 좌표값을 Node클래스에 담아서 각 list에 저장하면 백트래킹으로 구현이 가능하다.

		// 재귀 탈출 조건
		if(depth == M) {
			int sum = 0;

			for(int i=0; i<hsize; i++) {
				int temp = Integer.MAX_VALUE;

				for(int j=0; j<csize; j++) {

					// 남아있는 치킨집일 경우.
					if(visit[j]) {
                        if(temp == 1) break;
						int dist = Math.abs(houseList.get(i).x - chickenList.get(j).x) + Math.abs(houseList.get(i).y - chickenList.get(j).y);                                 
						temp = Math.min(temp,  dist);
					}
				}
				sum += temp;
			}

			result = Math.min(result, sum);
			return;
		}

재귀 탈출 조건은 depth가 M과 같을 때 검사에 들어간다.

각 집의 좌표값을 기준으로 현재 열려있는 치킨집 즉, visit이 true인 인덱스에 해당하는 chickenList의 좌표값을 기준으로 거리를 계산해서 최소값으로 갱신하면서, 전체 합을 계산하고,

sum과 result을 비교해서 최소값이 선택되면 마지막에 result를 출력하면 결과를 얻을 수 있다.

코드

---

Java

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

public class Main {
	static int N, M;
	static int result = Integer.MAX_VALUE;

	static int arr[][];
	static boolean visit[];
	static List<Node> houseList = new ArrayList<>();
	static List<Node> chickenList = new ArrayList<>();
	static int csize;
	static int hsize;

	static class Node {
		int x;
		int y;

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

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

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N][N];

		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				int num = Integer.parseInt(st.nextToken());

				if(num == 2) {
					chickenList.add(new Node(i, j, false));
				}
				else if(num == 1) {
					houseList.add(new Node(i, j, false));
				}
				arr[i][j] = num;
			}
		}

		csize = chickenList.size();
		hsize = houseList.size();

		// 치킨집의 개수만큼 방문여부를 확인하는 배열을 생성함
		visit = new boolean[csize];
		DFS(0, 0);

		System.out.println(result);
	} // End of main

	static void DFS(int index, int depth) {

		// 재귀 탈출 조건
		if(depth == M) {
			int sum = 0;

			for(int i=0; i<hsize; i++) {
				int temp = Integer.MAX_VALUE;

				for(int j=0; j<csize; j++) {

					// 남아있는 치킨집일 경우.
					if(visit[j]) {
                        if(temp == 1) break;
						int dist = Math.abs(houseList.get(i).x - chickenList.get(j).x) + Math.abs(houseList.get(i).y - chickenList.get(j).y);                                 
						temp = Math.min(temp,  dist);
					}
				}
				sum += temp;
			}

			result = Math.min(result, sum);
			return;
		}

		for(int i=index; i<csize; i++) {
			visit[i] = true;
			DFS(i+1, depth+1);
			visit[i] = false;
		}

	} // End of DFS	
} // End of Main class

Kotlin

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

private var N = 0; private var M = 0;
private var csize = 0; private var hsize = 0;
private var result = Integer.MAX_VALUE;

private lateinit var arr : Array<Array<Int>>
private lateinit var visit : Array<Boolean>
private var chickenList : MutableList<Node> = ArrayList<Node>();
private var houseList : MutableList<Node> = ArrayList<Node>();

private class Node(var x : Int, var y : Int)

fun main() {
    val br = BufferedReader( InputStreamReader(System.`in`) )
    var st : StringTokenizer;

    st = StringTokenizer(br.readLine());
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    arr = Array(N){Array(N) {0}}
    for(i in 0 until N) {
        st = StringTokenizer(br.readLine())
        for(j in 0 until N) {
            arr[i][j] = st.nextToken().toInt()

            if(arr[i][j] == 1) {
                houseList.add(Node(i, j));
            }
            else if(arr[i][j] == 2) {
                chickenList.add(Node(i, j));
            }
        }
    }

    csize = chickenList.size;
    hsize = houseList.size;
    visit = Array(csize, {false})

    DFS(0, 0)
    print(result)
} // End of main

private fun DFS(index : Int, depth : Int) {

    if (depth == M) {
        var sum = 0;

        for(i in 0 until hsize) {
            var temp = Integer.MAX_VALUE;

            for(j in 0 until csize) {
                if(visit[j]) {
                    if(temp == 1) break;

                    var dist = Math.abs(houseList.get(i).x - chickenList.get(j).x) + Math.abs(houseList.get(i).y - chickenList.get(j).y)
                    temp = Math.min(temp, dist)
                }
            }
            sum += temp;
        }

        result = Math.min(result, sum)
        return;
    }

    for(i in index until csize) {
        visit[i] = true;
        DFS(i+1, depth+1)
        visit[i] = false;
    }

} // End of DFS