13
๋ฐฑํธ๋ํน
๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ํ์ํ๋ ๋ฐฑํธ๋ํน ์๊ณ ๋ฆฌ์ฆ์ ๋ฐฐ์ ๋ด
์๋ค.
๋ฐฑํธ๋ํน ์
๋ฌธ ๋ฌธ์ 1
import java.util.Scanner;
public class Main {
public static int[] array;
public static boolean[] visit; //๋ฐฉ๋ฌธํ๋์ง ํ์ธ. default = False
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int M = scan.nextInt();
array = new int[M];
visit = new boolean[N];
dfs(N, M, 0);
}
public static void dfs(int N, int M, int depth) {
if (depth == M) {
for (int i=0; i< array.length; i++) {
System.out.print(array[i]+ " ");
}
System.out.println();
return;
}
for (int i = 0; i < N; i++) {
if (!visit[i]) {
visit[i] = true;
array[depth] = i + 1;
dfs(N, M, depth + 1);
visit[i] = false;
}
}
}
}
import java.util.Scanner;
public class Main {
static private int N, M;
static private boolean[] visit;
static private int[] array;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
N = scan.nextInt();
M = scan.nextInt();
//๋ฐฉ๋ฌธ์ฒ๋ฆฌ
visit = new boolean[N+1];
//๊ฐ์๋งํผ ์ถ๋ ฅํ ๊ฐ ๋ด์
array = new int[M];
dfs(0);
}
private static void dfs(int depth) {
//๊ฐ์ ๊ฐ์ผ๋ฉด ์ถ๋ ฅ
if (M == depth) {
for (int i=0; i<M; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
else {
for (int i=1; i<=N; i++) {
if (!visit[i]) {
if (depth == 0 || array[depth-1] < i) {
//d == 0์ ๋ค ์ถ๋ ฅ (1,2 | 1,3 | 1,4)
//์ด์ arr[]์์๊ฐ ํ์ฌ i๋ณด๋ค ์์ ๋
visit[i] = true; //๋ฐฉ๋ฌธ ์ฒ๋ฆฌ
array[depth] = i; //์์ ๋ด๊ธฐ
dfs(depth + 1); //์ฌ๊ท
//์์๋ณต๊ตฌ
visit[i] = false;
}
}
}
}
}
}
import java.util.Scanner;
public class Main {
static private int N, M;
static private int[] array;
static public StringBuilder sb =new StringBuilder();
public static void dfs(int depth) {
if (M == depth) {
for (int i=0; i<M; i++) {
sb.append(array[i] + " ");
}
sb.append('\n');
return;
}
else {
for (int i=1; i<=N; i++) {
array[depth] = i; //์์ ๋ด๊ธฐ
dfs(depth+1); //์ฌ๊ท
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
N = scan.nextInt();
M = scan.nextInt();
array = new int[M];
dfs(0);
System.out.println(sb);
}
}
import java.util.Scanner;
public class Main {
static public int N, M, now;
static public int[] array;
public static void dfs(int now, int depth) {
if (M == depth) {
for (int i=0; i<M; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
return;
}
for (int i=now; i<=N; i++) {
array[depth] = i;
dfs(now++, depth+1); //์ฌ๊ท
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
N = scan.nextInt();
M = scan.nextInt();
array = new int [N];
dfs(1, 0);
}
}
์กฐ๊ธ ๋ ๋ณต์กํ ๋ฐฑํธ๋ํน ๋ฌธ์ 1
import java.util.Scanner;
public class Main {
public static int count = 0;
public static int array[];
public static int queen;
public static boolean condition(int col) {//์กฐ๊ฑด
for(int i = 0; i<col; i++) {
if(array[i] == array[col]) return false; //๊ฐ์ ์ด์ด๋ฉด
if((array[i] - array[col]) == (col - i)) return false; //์ค๋ฅธ์ชฝ์๋ ๋๊ฐ์ ๋ฐฉํฅ์ด๋ฉด
if((array[col] - array[i]) == (col-i)) return false; //์ผ์ชฝ์๋ ๋๊ฐ์ ๋ฐฉํฅ์ด๋ฉด
//if(Math.abs(col-i) == Math.abs(array[col] - array[i])) return false; // ๋ชจ๋ ๋๊ฐ์ ๋ฐฉํฅ
}
return true;
}
public static void backtracking(int depth) {
if(depth == queen) // ๋๊น์ง ๊ฐ๋ฉด ์นด์ดํธ
count++;
else {
for(int i=0; i<queen; i++) {
array[depth] = i;
if(condition(depth))
backtracking(depth+1);
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
queen = scan.nextInt();
array = new int [queen];
backtracking(0);
System.out.println(count);
}
}
์กฐ๊ธ ๋ ๋ณต์กํ ๋ฐฑํธ๋ํน ๋ฌธ์ 2
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
static int array[][] = new int [9][9];
static ArrayList<int []> list = new ArrayList<int[]>();
public static void backTracking(int depth) {
if(depth == list.size()) {
for(int i=0; i<9; i++) {
for(int j =0; j<9; j++) {
System.out.print(array[i][j] + " ");
}
System.out.println();
}
System.exit(0);
}
else {
int x = list.get(depth)[0];
int y = list.get(depth)[1];
for(int i = 1; i<=9; i++) {
if(check(x,y,i)) {
array[x][y] = i;
backTracking(depth+1);
array[x][y] = 0;
}
}
}
}
public static boolean check(int x, int y, int num) {
for(int i=0; i<9; i++)
if(array[x][i] == num) return false;
for(int i=0; i<9; i++)
if(array[i][y]==num) return false;
int xx = x/3 *3;
int yy = y/3 *3;
for(int i= xx; i<xx+3; i++)
for(int j = yy; j<yy+3; j++)
if(num == array[i][j]) return false;
return true;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
for(int i = 0; i<9; i++) //2์ฐจ์ ๋ฐฐ์ด ์
๋ ฅ๋ฐ์.
for(int j=0; j<9; j++)
if((array[i][j] = scan.nextInt()) ==0)
list.add(new int [] {i,j});
backTracking(0);
}
}