[BOJ] BackTracking /13단계

13

백트래킹

모든 경우를 탐색하는 백트래킹 알고리즘을 배워 봅시다.

---

1

15649

N과 M (1)

백트래킹 입문 문제 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;
			}
		}
	}
 
}

---

2

15650

N과 M (2)

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;
					}
				}
			}
		}
		
	}
}

---

3

15651

N과 M (3)

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);
	}

}

---

4

15652

N과 M (4)

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);
	}
}

---

 

5

9663

N-Queen

조금 더 복잡한 백트래킹 문제 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);
	}
}

---

6

2580

스도쿠

조금 더 복잡한 백트래킹 문제 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);
	
	}

}