백준 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
를 출력하면 결과를 얻을 수 있다.
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
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