백트래킹 알고리즘 (Backtracking Algorithm)

🧭 백트래킹 알고리즘 (Backtracking Algorithm)

📌 개념 요약

백트래킹은 가능한 모든 경우를 탐색하되, 조건에 맞지 않는 경우를 미리 제외하여 효율적으로 해답을 찾는 방식이다. 즉, 조건에 부합하지 않는 경로는 더 이상 탐색하지 않고 이전 단계로 돌아가 다른 경로를 탐색한다.

알고리즘 흐름도

[시작]
   ↓
[문제와 입력값 정의]
   ↓
[가능한 선택을 하나 생성]
   ↓
[선택이 유효한가?]
   ↓
[예] → [선택을 저장하고 다음 단계로 이동]
[아니오] → [이전 단계로 되돌아감]
   ↓
[모든 선택이 완료되었는가?]
   ↓
[최종 해답 출력]
   ↓
[종료]

---

예제: N-Queen 문제

문제 설명:

N×N 체스판에 N개의 퀸을 서로 공격하지 않도록 배치하는 방법의 수를 구하시오.

N=4일 때:

int N = 4;  				// 체스판 크기 (4x4)
int[] board = new int[N];  	// 각 행에 배치된 퀸의 열을 저장할 배열
int count = 0;  			// 가능한 배치의 수

// 퀸을 배치할 행을 하나씩 탐색
void solve(int row) {
    if (row == N) {  		// 모든 행에 퀸을 배치했다면
        count++;  			// 하나의 유효한 해답을 찾은 것
        return;
    }
    // 각 열에 대해 퀸을 배치해본다
    for (int col = 0; col < N; col++) {
        board[row] = col;  	// 현재 행에 퀸을 배치
        if (isValid(row)) { // 배치가 유효한지 확인
            solve(row + 1); // 다음 행으로 퀸을 배치
        }
    }
}

// 배치가 유효한지 검사하는 함수
boolean isValid(int row) {
    for (int i = 0; i < row; i++) {  // 이미 배치된 행들과 비교
        // 같은 열에 퀸이 있거나 대각선 상에 퀸이 있으면 안 된다
        if (board[i] == board[row] || Math.abs(board[i] - board[row]) == row - i) {
            return false;  	// 유효하지 않다면 false 반환
        }
    }
    return true;  			// 유효한 배치라면 true 반환
}

// 퀸을 배치하기 시작
solve(0);

// 가능한 배치의 수를 출력
System.out.println("해답의 수: " + count);

→ 각 행에 퀸을 하나씩 배치하면서, 이전에 배치된 퀸들과의 충돌 여부를 확인한다. 충돌이 발생하면 이전 단계로 되돌아가 다른 위치에 퀸을 배치하는 방식으로 모든 가능한 배치를 탐색한다.

주석 해설

1. 재귀 함수 solve는 각 행에서 퀸을 배치하고, 유효한 배치가 확인되면 다음 행으로 넘어가서 퀸을 배치한다.

2. 유효성 검사(isValid 함수)는 이전에 배치한 퀸들과의 충돌 여부(같은 열이나 대각선 상에 배치되는지)를 검사.

3. 모든 행에 퀸을 배치한 경우, 하나의 유효한 해답을 찾았다고 판단하고, 해답 수를 증가시킨다.

✨알고리즘 흐름

1. 문제 정의 및 입력값 설정

체스판 크기 N과 퀸을 배치할 배열 board를 정의한다.

int N = 4;  // 체스판 크기 (4x4)
int[] board = new int[N];  // 각 행에 배치된 퀸의 열을 저장할 배열
int count = 0;  // 가능한 배치의 수

2. 초기화 및 백트래킹 함수 시작

백트래킹 함수를 정의하여 각 행에 퀸을 배치한다.

void solve(int row) {
    // 모든 행에 퀸을 배치했으면
    if (row == N) {
        count++;  // 유효한 배치 하나를 찾은 것
        return;
    }
    
    // 각 열에 대해 퀸을 배치할 수 있는지 확인
    for (int col = 0; col < N; col++) {
        board[row] = col;  // 현재 행에 퀸을 배치
        if (isValid(row)) {  // 배치가 유효하다면
            solve(row + 1);  // 다음 행으로 넘어가서 퀸을 배치
        }
    }
}

3. 각 열에 대해 퀸 배치 시도

solve() 함수에서 각 열을 순차적으로 탐색하고 퀸을 배치한다.

for (int col = 0; col < N; col++) {
    board[row] = col;  // 현재 행에 퀸을 배치
    if (isValid(row)) {  // 유효한 배치라면
        solve(row + 1);  // 다음 행으로 이동하여 퀸을 배치
    }
}

4. 배치가 유효한지 확인 (유효성 검사)

isValid() 함수는 퀸을 배치한 후, 배치가 유효한지 검사하는 함수로 같은 열, 대각선에 퀸이 있는지 확인한다.

boolean isValid(int row) {
    for (int i = 0; i < row; i++) {  // 이미 배치된 행들과 비교
        // 같은 열에 퀸이 있거나 대각선 상에 퀸이 있으면 안 된다
        if (board[i] == board[row] || Math.abs(board[i] - board[row]) == row - i) {
            return false;  // 유효하지 않다면 false 반환
        }
    }
    return true;  // 유효한 배치라면 true 반환
}

5. 유효하다면 다음 행으로 이동

배치가 유효한 경우, 다음 행으로 이동해서 퀸을 배치한다. solve(row + 1)을 호출하여 재귀적으로 진행.

solve(row + 1);  // 다음 행으로 넘어가서 퀸을 배치

6. 모든 행에 퀸을 배치했을 때

모든 행에 퀸을 배치한 경우, 유효한 해답을 찾은 것으로 간주하고 count를 증가시킨다.

if (row == N) {
    count++;  // 유효한 해답 하나를 찾은 것
    return;
}

7. 백트래킹 (되돌리기)

만약 퀸을 배치할 수 없는 경우, 이전 행으로 돌아가서 다른 열에 퀸을 배치한다.

백트래킹은 주로 solve() 함수 내에서 재귀적으로 호출하면서 진행되며, 이전에 시도했던 열에서 더 이상 배치할 수 없으면 다른 열을 시도하거나, 다른 행으로 돌아가서 다시 시도한다.

8. 반복 및 종료

모든 가능한 배치를 시도한 후, 결과를 출력한다.

System.out.println("가능한 배치 수: " + count);