0. DFS - Combination
조합을 구할때 DFS방식으로 구하는 경우이다.
depth만큼 dfs를 돌아서 arr배열에 담는 것이다.
ex) 1 2 3 를 2개씩 뽑는 경우의 수 (중복 제외)
1 2
1 3
2 3
이렇게 3가지이다.
public static void dfs(int depth, int start, int[] arr) {
if(depth == K) {
combList.add(arr.clone());
return;
}
for(int i = start; i < N; i++) {
if(!visit[i]) {
visit[i] = true;
arr[depth] = i;
dfs(depth+1, i+1, arr);
visit[i] = false;
}
}
}따라서 위 경우 depth=2가 되고 arr[]에는 [1, 2] , [1, 3], [2, 3]이 되고 이를 combList(ArrayList<int[]>)에 담으면
combList:
0 : [1, 2]
1 : [1, 3]
2 : [2, 3]
이렇게 된다.
[1, 2]의 경우 남은건 3 이기 때문에 rest배열에 남은걸 넣어준다.
- check는 남은 번호를 알기위한 배열. comb에 있는 숫자를 먼저 true로 체크하고, true가 아닌 숫자들만 rest배열에 담는다.
▼코드
dfs(0, 0, new int[K]);
int answer = Integer.MAX_VALUE;
for(int comb[] : combList) {
int rest[] = new int[N - K];
boolean check[] = new boolean[N];
for(int choice : comb) {
check[choice] = true;
}
int index = 0;
for(int i = 0; i < N; i++) {
if(!check[i]) {
rest[index] = i;
index++;
}
}
}1. 문제
1-1. 백준 '대피소'
1-2. 프로그래머스 '주사위 고르기'
1-3. 백준 '치킨배달'
2. 풀이
2-1. [백준 '대피소']
- 대피소를 설치할 집을 dfs로 구한다.
- 대피소가 아닌 집과 대피소간의 거리를 파악하여 최소거리를 구한다.
rest[] : 대피소 아닌 집들의 번호
comb[] : 대피소인 집 번호int max = Integer.MIN_VALUE; for(int i = 0; i < rest.length; i++) { Node n1 = house.get(rest[i]); int gap = 0; int min = Integer.MAX_VALUE; for(int j = 0; j < comb.length; j++) { Node n2 = house.get(comb[j]); gap = Math.abs(n1.x - n2.x) + Math.abs(n1.y - n2.y); min = Math.min(min, gap); // 남은 집 - 대피소간의 최소 거리를 구한다 } max = Math.max(max, min); // 최소 거리들중의 최대를 구한다. } answer = Math.min(answer, max); // 최대 거리들 중 가장 작은 값을 구한다.
2-1. [백준 '치킨배달']
도시의 치킨집중 최대 M개를 고르는 방법.
- ArrayList를 2개 만들어서 1일경우 houseList에, 2일경우 chickenList에 담는다.
for(int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine(), " "); for(int j = 0; j < N; j++) { int index = Integer.parseInt(st.nextToken()); if(index == 1) { houseList.add(new Node(i, j)); } else if(index == 2) { chickenList.add(new Node(i, j)); } } }
- dfs로 M개만큼 치킨집을 골라준다.
- 각 조합의 경우로 최소거리를 구한다.
3. 코드
3-1. [백준 '대피소']
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int K;
static ArrayList<Node> house = new ArrayList<>();
static ArrayList<int[]> combList = new ArrayList<>();
static boolean visit[];
public static class Node{
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
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());
K = Integer.parseInt(st.nextToken());
visit = new boolean[N];
for(int n = 0; n < N; n++) {
st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
house.add(new Node(x, y));
}
dfs(0, 0, new int[K]);
int answer = Integer.MAX_VALUE;
for(int comb[] : combList) {
int rest[] = new int[N - K];
boolean check[] = new boolean[N];
for(int choice : comb) {
check[choice] = true;
}
int index = 0;
for(int i = 0; i < N; i++) {
if(!check[i]) {
rest[index] = i;
index++;
}
}
int max = Integer.MIN_VALUE;
for(int i = 0; i < rest.length; i++) {
Node n1 = house.get(rest[i]);
int gap = 0;
int min = Integer.MAX_VALUE;
for(int j = 0; j < comb.length; j++) {
Node n2 = house.get(comb[j]);
gap = Math.abs(n1.x - n2.x) + Math.abs(n1.y - n2.y);
min = Math.min(min, gap);
}
max = Math.max(max, min);
}
answer = Math.min(answer, max);
}
System.out.println(answer);
}
public static void dfs(int depth, int start, int[] arr) {
if(depth == K) {
combList.add(arr.clone());
return;
}
for(int i = start; i < N; i++) {
if(!visit[i]) {
visit[i] = true;
arr[depth] = i;
dfs(depth+1, i+1, arr);
visit[i] = false;
}
}
}
}
3-2. [프로그래머스 '주사위 던지기'] 코드
import java.util.*;
class Solution {
static int n;
static int answer[];
static boolean check[];
static List<int[]> diceComb;
static List<Integer> scoreA;
static List<Integer> scoreB;
public static int[] solution(int[][] dice) {
n = dice.length;
answer = new int[n / 2];
check = new boolean[n];
diceComb = new ArrayList<>();
int max = Integer.MIN_VALUE;
//1. dfs로 경우의 수 구하기
dfs(0, 0, new int[n / 2]);
//2. B의 경우도 구해주기.
for(int[] combA : diceComb) {
ArrayList<Integer> other = new ArrayList<>();
int []combB = new int[n / 2];
for(int choice : combA) {
other.add(choice);
}
int index = 0;
for(int i = 0; i < n; i++) {
if(!other.contains(i)) {
combB[index] = i;
index++;
}
}
// 3. 각 combA, combB로 계산합 구하기.
scoreA = new ArrayList<>();
scoreB = new ArrayList<>();
combDice(0, combA, dice, 0, scoreA);
combDice(0, combB, dice, 0, scoreB);
Collections.sort(scoreA);
Collections.sort(scoreB);
// 4. 각 합을 이진탐색으로 비교하기.
int totalWinCount = 0;
for(Integer a : scoreA) {
int left = 0;
int right = scoreB.size();
while(left + 1 < right) {
int mid = (left + right) / 2;
if(a > scoreB.get(mid)) {
left = mid;
} else {
right = mid;
}
}
totalWinCount += left;
}
if(totalWinCount > max) {
max = totalWinCount;
answer = combA;
}
}
int answer2[] = new int[n / 2];
for(int i = 0; i < answer.length; i++) {
answer2[i] = answer[i] + 1;
}
return answer2;
}
public static void dfs(int depth, int start, int[] arr) {
if(depth == n / 2) {
diceComb.add(arr.clone());
return;
}
for(int i = start; i < n; i++) {
if(!check[i]) {
check[i] = true;
arr[depth] = i;
dfs(depth+1, i+1, arr);
check[i] = false;
}
}
}
public static void combDice(int index, int[] dices, int[][] originDices, int sum, List<Integer> team) {
if(index == dices.length) {
team.add(sum);
return;
}
for(int i = 0; i < 6; i++) { // 6가지 면에 대해서 구하는 것.
combDice(index+1, dices, originDices, sum + originDices[dices[index]][i], team);
}
}
}
3-3. [백준 '치킨 배달'] 코드
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int M;
static ArrayList<Node> chickenList = new ArrayList<>();
static ArrayList<Node> houseList = new ArrayList<>();
static ArrayList<int[]> combList = new ArrayList<>();
static boolean[] visit;
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());
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j = 0; j < N; j++) {
int index = Integer.parseInt(st.nextToken());
if(index == 1) {
houseList.add(new Node(i, j));
} else if(index == 2) {
chickenList.add(new Node(i, j));
}
}
}
visit = new boolean[chickenList.size()];
dfs(0, 0, new int[M]);
int totalMin = Integer.MAX_VALUE;
for(int[] comb : combList) {
int sum = 0;
for(int i = 0; i < houseList.size(); i++) {
int houseX = houseList.get(i).x;
int houseY = houseList.get(i).y;
int min = (N - 1) * 2;
for(int j = 0; j < comb.length; j++) {
int chickenX = chickenList.get(comb[j]).x;
int chickenY = chickenList.get(comb[j]).y;
int gap = Math.abs(houseX - chickenX) + Math.abs(houseY - chickenY);
min = Math.min(min, gap);
}
sum += min;
}
totalMin = Math.min(totalMin, sum);
}
System.out.println(totalMin);
}
public static void dfs(int depth, int start, int arr[]) {
if(depth == M) {
combList.add(arr.clone());
return;
}
for(int i = start; i < visit.length; i++) {
if(!visit[i]) {
visit[i] = true;
arr[depth] = i;
dfs(depth+1, i+1, arr);
visit[i] = false;
}
}
}
public static class Node{
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
}
Hi!