백준 2422번
https://www.acmicpc.net/problem/2422
한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다.
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken());
int num2 = Integer.parseInt(st.nextToken());
comb[num][num2] = true;
comb[num2][num] = true;
}
피해야 하는 조합을 파악하기 위해서 미리 boolean형 comb
2차원 배열을 만들어뒀다.
입력받는 조합의 값을 인덱스로 받아서 comb
배열에 true값으로 저장하면 된다.
이렇게 하면 나중에 백트래킹을 통한 탐색으로 만들어진 조합을 다시 인덱스 값으로 넣어서 해당 조합의 값이 true인지 아닌지만 검사하면 된다.
if(depth == 3) {
for(int i=0; i<3; i++) {
for(int j=0; j<3; j++) {
if(comb[ans[i]][ans[j]]) {
return;
}
}
}
result++;
return;
}
재귀 탈출조건인 depth
가 3일 경우,
ans
배열을 인덱스 값으로 사용하여 comb
배열을 탐색한다.
한번이라도 true가 생기면 피해야하는 조합이므로 곧바로 return 한다.
피하지 않아도 되는 조합일 경우, result
를 증가시킨다.
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static boolean comb[][];
static int arr[];
static boolean visit[];
static int ans[];
static int result = 0;
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+1];
visit = new boolean[N+1];
comb = new boolean[N+1][N+1]; // 조합을 담는 배열
ans = new int[3]; // 백트래킹 정답 담는 배열
for(int i=1; i<=N; i++) arr[i-1] = i;
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken());
int num2 = Integer.parseInt(st.nextToken());
comb[num][num2] = true;
comb[num2][num] = true;
}
DFS(0, 0);
System.out.println(result);
} // End of main
private static void DFS(int idx, int depth) { // 백트래킹
if(depth == 3) {
for(int i=0; i<3; i++) {
for(int j=0; j<3; j++) {
if(comb[ans[i]][ans[j]]) {
return;
}
}
}
result++;
return;
}
for(int i=idx; i<N; i++) {
if(visit[i]) continue;
visit[i] = true;
ans[depth] = arr[i];
DFS(i+1, depth+1);
visit[i] = false;
}
} // End of DFS
} // End of Main class
import java.util.*
import java.io.*
private var N = 0; private var M = 0
private lateinit var arr : IntArray
private lateinit var visit : BooleanArray
private lateinit var comb : Array<BooleanArray>
private lateinit var ans : IntArray
private var result = 0
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
var st = StringTokenizer(br.readLine())
N = st.nextToken().toInt(); M = st.nextToken().toInt()
arr = IntArray(N+1)
visit = BooleanArray(N+1)
comb = Array(N+1){ BooleanArray(N+1) }
ans = IntArray(3)
for(i in 1..N) arr[i-1] = i
for(i in 0 until M) {
st = StringTokenizer(br.readLine())
var x = st.nextToken().toInt()
var y = st.nextToken().toInt()
comb[x][y] = true; comb[y][x] = true
}
DFS(0, 0);
print(result)
} // End of main
private fun DFS(index : Int, depth : Int) {
if(depth == 3) {
for(i in 0 until 3) {
for(j in 0 until 3) {
if(comb[ans[i]][ans[j]]) return
}
}
result++
return
}
for(i in index until N) {
if(visit[i]) continue;
visit[i] = true
ans[depth] = arr[i]
DFS(i+1, depth+1)
visit[i] = false
}
} // End of DFS