-
[알고리즘] 백트래킹(Backtracking) | 백준 9663. N-Queen _Java알고리즘 2023. 8. 17. 14:49728x90반응형
백트래킹(Backtracking) 알고리즘
백트래킹 알고리즘이란?
백트래킹은 조합 최적화, 문제 해결 등 여러 문제에서 사용되는 알고리즘 기법 중 하나입니다. 주로 모든 가능한 경우의 수를 탐색하면서 해답을 찾는데 사용되며, 문제의 조건을 만족하지 않으면 해당 경로를 포기하고 이전 단계로 돌아가는 방식으로 동작합니다.
백트래킹 알고리즘 구현 단계
- 선택 (Choose): 다음으로 시도할 선택을 하거나, 다음 상태로 진행합니다.
- 조건 확인 (Constraint): 선택한 것이 조건을 만족하는지 확인합니다.
- 해결 여부 판단 (Is it a solution?): 현재 선택과 조건이 문제의 해결을 이끌어냈는지 확인합니다.
- 해결하지 못한 경우 (No): 선택한 것이 조건을 만족하지 않으면 이전 상태로 돌아갑니다.
- 해결한 경우 (Yes): 문제가 해결되었다면 결과를 출력하거나 저장합니다.
- 반복 (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; } }
LIST'알고리즘' 카테고리의 다른 글
[알고리즘] Dynamic Programming(동적 계획법, DP) | 백준 1463. 1로 만들기 _Java (0) 2023.08.29 [알고리즘] 병합 정렬(Merge Sort) vs 퀵 정렬(Quick Sort) (0) 2023.06.28 [algorithm] 분할 정복 알고리즘 Divide and Conquer (2) 2023.06.27