[알고리즘] 백트래킹(Backtracking) | 백준 9663. N-Queen _Java

 

백트래킹(Backtracking) 알고리즘

 

백트래킹 알고리즘이란?

백트래킹은 조합 최적화, 문제 해결 등 여러 문제에서 사용되는 알고리즘 기법 중 하나입니다. 주로 모든 가능한 경우의 수를 탐색하면서 해답을 찾는데 사용되며, 문제의 조건을 만족하지 않으면 해당 경로를 포기하고 이전 단계로 돌아가는 방식으로 동작합니다.

 

 

백트래킹 알고리즘 구현 단계

1. 선택 (Choose): 다음으로 시도할 선택을 하거나, 다음 상태로 진행합니다.
2. 조건 확인 (Constraint): 선택한 것이 조건을 만족하는지 확인합니다.
3. 해결 여부 판단 (Is it a solution?): 현재 선택과 조건이 문제의 해결을 이끌어냈는지 확인합니다.
4. 해결하지 못한 경우 (No): 선택한 것이 조건을 만족하지 않으면 이전 상태로 돌아갑니다.
5. 해결한 경우 (Yes): 문제가 해결되었다면 결과를 출력하거나 저장합니다.
6. 반복 (Iterate): 다음 경우의 수를 확인하기 위해 다시 1단계로 돌아갑니다.

 

Java로 구현하기

N-Queen 문제

N-퀸 문제는 대표적인 백트래킹 알고리즘을 사용하는 문제입니다.

N x N 크기의 체스판 위에 N개의 퀸을 서로 공격하지 않도록 배치하는 방법의 횟수를 출력하는 문제입니다.

import java.util.*;
import java.io.*;

public class Main {
	static int N, col[], ans;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		col = new int[N+1]; // 1열부터 사용
		ans = 0; // 가능한 경우의 수
		
		setQueen(1);
		System.out.println(ans);
	}
	
	// 해당 퀸을 현재 행에 가능한 모든 곳에 놓아보기
	private static void setQueen(int row) {
		// 가지 치기
		if(!isAvailable(row-1)) return;
		// 기저 조건
		if(row>N) {
			ans++;
			return;
		}
		
		// 유도파트
		for (int c = 1; c <= N; c++) {
			col[row] = c;
			setQueen(row+1);
		}
		
	}
	
	private static boolean isAvailable(int row) { // row: 마지막으로 놓아진 퀸의 행
		for (int i = 1; i < row; i++) {
			if(col[i] == col[row] || row-i == Math.abs(col[row] - col[i])) {
				return false;
			}
		}
		return true;
	}

}

 

 

 

https://www.acmicpc.net/problem/9663

9663번: N-Queen