일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 이터레이터
- network configuration
- 스프링부트핵심가이드
- 처음 만나는 AI 수학 with Python
- 코드로배우는스프링부트웹프로젝트
- ㅒ
- 친절한SQL튜닝
- 네트워크 설정
- 목록처리
- 선형대수
- 데비안
- d
- 코드로배우는스프링웹프로젝트
- 자료구조와함께배우는알고리즘입문
- 서버설정
- 스프링 시큐리티
- iterator
- /etc/network/interfaces
- 티스토리 쿠키 삭제
- 자료구조와 함께 배우는 알고리즘 입문
- 페이징
- resttemplate
- 처음 만나는 AI수학 with Python
- 리눅스
- 알파회계
- Kernighan의 C언어 프로그래밍
- 자바편
- GIT
- 구멍가게코딩단
- baeldung
- Today
- Total
bright jazz music
백트래킹 알고리즘(backtracking algorithms) 본문
백트래킹 알고리즘(backtracking algorithms)
bright jazz music 2024. 11. 11. 13:35백트래킹은 가능한 모든 해결책을 탐색하면서, 현재 선택이 잘못된 방향으로 가고 있다고 판단되면 이전 단계로 돌아가서(백트랙) 다른 선택을 시도하는 알고리즘이다.
N-Queen 문제를 대표적인 예로 들 수 있다. N-Queen 문제는 체스판 위에 N개의 퀸을 배치하는 문제이다. 어떤 두 퀸도 같은 행, 열, 또는 대각선에 위치하지 않도록 하는 모든 가능한 배치를 찾는 것이다. 만약 같은 행, 열, 대각선에 하나라도 위치하게 된다면 일치한 퀸은 서로가 공격할 수 있는 상황에 노출된다. 이 문제에서는 각 행에 퀸을 배치하면서 이미 배치된 퀸과 충돌하지 않는 위치를 찾는다. 만약 충돌하지 않는 위치가 없다면 그 행에 대한 배치를 포기하고 이전 행으로 돌아가 다른 위치를 시도한다. 이러한 방식을 시도하면 모든 가능한 배치를 시도하지 않고도 문제의 해결책을 찾을 수 있다.
// N-Queen 문제: N x N 체스판에 N개의 퀸을 서로 공격할 수 없게 배치하는 문제
// 퀸은 가로, 세로, 대각선으로 움직일 수 있다
// 4x4 체스판의 경우 2가지 해답이 존재한다
function solveNQueens(n) {
// Array(n).fill()로 n개의 행을 만들고,
// 각 행마다 map을 통해 n개의 열을 만들어 2차원 배열 생성
// '.'은 빈칸, 'Q'는 퀸의 위치를 나타냄
const board = Array(n).fill().map(() => Array(n).fill('.'));
/*
[
[ '.', '.', '.', '.' ],
[ '.', '.', '.', '.' ],
[ '.', '.', '.', '.' ],
[ '.', '.', '.', '.' ]
]
*/
const solutions = [];
// 퀸을 놓을 수 있는지 확인하는 함수
// 이전 행들만 확인하면 됨 (현재 행 위쪽만 체크)
// 1. 같은 열에 퀸이 있는지 체크
// 2. 왼쪽 대각선에 퀸이 있는지 체크 (row-1, col-1 방향)
// 3. 오른쪽 대각선에 퀸이 있는지 체크 (row-1, col+1 방향)
// 세 방향 모두 퀸이 없어야 true 반환
function isValid(row, col) {
// 같은 열 체크
for (let i = 0; i < row; i++) {
if (board[i][col] === 'Q') return false;
}
// 왼쪽 대각선 체크
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] === 'Q') return false;
}
// 오른쪽 대각선 체크
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] === 'Q') return false;
}
return true;
}
// row는 현재 확인중인 행
// n개의 퀸을 모두 배치했다면(row === n) 해답 배열에 추가
// 각 행마다 가능한 모든 열(0 ~ n-1)에 퀸을 놓아보며 진행
// 1. 현재 위치가 유효하면(isValid) 퀸 배치
// 2. 다음 행으로 재귀 호출
// 3. 백트래킹: 재귀 호출이 끝나면 현재 위치의 퀸 제거
function backtrack(row) {
// 기저 조건: 모든 행에 퀸을 배치했으면 해답 추가
if (row === n) {
solutions.push(board.map(row => row.join(''))); // .Q..
return;
}
// 현재 행의 각 열에 퀸을 놓아보기
for (let col = 0; col < n; col++) {
if (isValid(row, col)) { // 좌표를 방사형으로 체크했을 때 퀸이 없다면 true
board[row][col] = 'Q'; // 퀸 배치
backtrack(row + 1); // 다음 행으로 진행 (재귀 호출로 인한 대기/waiting)
// 이 지점에서 현재 프로세스가 대기 상태가 되고
// 재귀적으로 다음 행들을 체크하는 작업 진행
board[row][col] = '.'; // 재귀 호출 완료(해답 찾거나 실패) 후 퀸 제거(백트래킹)
// 대기하던 작업이 완료된 후 현재 상태 초기화
}
}
}
// 백트래킹 시작: 0번 행부터 시작
backtrack(0);
return solutions;
}
// 시간 복잡도: O(N!)
// 각 행마다 N개의 열을 확인하고, 유효한 위치를 찾아 재귀적으로 진행
// 실제로는 가지치기(pruning)로 인해 N!보다는 적은 경우의 수를 확인
// 사용 예시
console.log(solveNQueens(4));
/*
출력 결과:
[
[ '.Q..', '...Q', 'Q...', '..Q.' ], // 아래와 같은 체스판을 의미
[ '..Q.', 'Q...', '...Q', '.Q..' ] // . Q . .
] // . . . Q
// Q . . .
// . . Q .
위 2차원 배열은 퀸을 겹치지 않고 배치하는 방법이 두 가지임을 의미한다.
각 원소 배열이 하나의 솔루션을 의미한다.
*/
위 코드에서는, 체스판의 각 행을 순회하면서 퀸을 배치한다. 각 위치에서는 isValid 함수를 사용하여 해당 위치에 퀸을 배치할 수 있는지 확인한다. 퀸을 배치할 수 있는 위치를 찾으면 퀸을 배치하고 다음 행으로 이동한다. 만약 행의 모든 위치가 유효하지 않다면 이전 행으로 돌아가 퀸의 위치를 변경한다. 이러한 방식을 통해 모든 행에 퀸을 배치할 수 있는 모든 경우의 수를 찾을 수 있다.
구체적으로는,
1. 행(row) 기준 순회
- 0번 행부터 시작해서 마지막 행까지 순차적으로 진행
- 각 행에서는 모든 열(col)을 검사
2. 유효성 검사 (isValid 함수)
- 현재 위치(row, col)에 퀸을 놓을 수 있는지 검사
- 같은 열, 왼쪽 대각선, 오른쪽 대각선에 다른 퀸이 없어야 함
3. 백트래킹 과정
if (isValid(row, col)) {
board[row][col] = 'Q'; // 퀸 배치
backtrack(row + 1); // 다음 행으로 진행
board[row][col] = '.'; // 실패시 퀸 제거하고 다음 열 시도
}
- 유효한 위치면 퀸을 배치하고 다음 행으로
- 유효한 위치가 없거나 더 이상 진행이 불가능하면 이전 상태로 돌아가기
- 이전 상태로 돌아갈 때는 배치했던 퀸을 제거(백트래킹)
4. 해답 찾기
- 마지막 행(row === n)까지 도달하면 유효한 해답을 찾은 것
- 찾은 해답을 solutions 배열에 저장
이것이 백트래킹의 핵심 매커니즘이다.
"시도 -> 실패 -> 되돌아가기 -> 다시 시도" 의 과정을 반복하면서 모든 가능한 해답을 찾아내는 것이다.
예제2: 기사를 위한 자리
N-Queen 문제와 유사하다. knight는 L자 형태로 움직인다. 따라서 나이트가 서로 공격할 수 없다는 것은 어떤 두 나이트도 L자 형태의 움직임으로 이동할 수 있는 위치에 있지 않도록 배치해야 한다는 의미이다.
// n x n 체스판에 나이트를 서로 공격할 수 없게 배치하는 문제
function solveKnight(n) {
// n x n 크기의 2차원 배열 생성, '.'으로 초기화
let board = Array(n)
.fill()
.map(() => Array(n).fill('.'));
// 최종 해답을 저장할 배열
let solution = [];
// 나이트가 이동할 수 있는 8가지 방향 정의
// dx, dy 쌍이 L자 형태의 이동을 표현
let dx = [-2, -1, 1, 2, -2, -1, 1, 2]; // 행 방향 이동
let dy = [1, 2, 2, 1, -1, -2, -2, -1]; // 열 방향 이동
// 현재 위치(i,j)에 나이트를 놓을 수 있는지 확인하는 함수
// 다른 나이트의 공격 범위에 있으면 true 반환
function isAttack(i, j) {
// 8방향을 모두 체크
for(let k = 0; k < 8; k++) {
let x = i + dx[k];
let y = j + dy[k];
// 체스판 범위 내에 있고, 해당 위치에 나이트('K')가 있는지 확인
if(x >= 0 && y >= 0 && x < n && y < n && board[x][y] === 'K') {
return true; // 공격 가능한 나이트가 있음
}
}
return false; // 공격 가능한 나이트가 없음
}
// 백트래킹으로 나이트를 배치하는 함수
// row: 현재 처리중인 행
function backtrack(row) {
// 기저 조건: 모든 행을 다 처리했으면 해답에 추가
if(row === n) {
solution.push(board.map(row => row.join('')));
return;
}
// 현재 행의 각 열을 순회하면서 나이트 배치 시도
for(let col = 0; col < n; col++) {
if(!isAttack(row, col)) { // 현재 위치에 나이트를 놓을 수 있다면
board[row][col] = 'K'; // 나이트 배치
backtrack(row + 1); // 다음 행으로 진행 (재귀 호출로 인한 스레드 대기)
board[row][col] = '.'; // 재귀 호출 완료 후 나이트 제거 (백트래킹)
}
}
}
// 0번 행부터 백트래킹 시작
backtrack(0);
return solution;
}
// 4x4 체스판에서 해답 찾기
console.log(solveKnight(4));
/*
[
[ 'K...', 'K...', 'K...', 'K...' ],
[ 'K...', 'K...', 'K...', '...K' ],
[ 'K...', 'K...', '...K', 'K...' ],
[ 'K...', 'K...', '...K', '..K.' ],
[ 'K...', 'K...', '...K', '...K' ],
[ 'K...', '.K..', 'K...', '.K..' ],
[ 'K...', '.K..', 'K...', '...K' ],
[ 'K...', '.K..', '..K.', '.K..' ],
[ 'K...', '.K..', '..K.', '...K' ],
[ 'K...', '...K', 'K...', 'K...' ],
[ 'K...', '...K', 'K...', '.K..' ],
[ 'K...', '...K', 'K...', '...K' ],
[ 'K...', '...K', '..K.', '.K..' ],
[ 'K...', '...K', '..K.', '...K' ],
[ 'K...', '...K', '...K', 'K...' ],
[ 'K...', '...K', '...K', '...K' ],
[ '.K..', 'K...', '.K..', 'K...' ],
[ '.K..', 'K...', '.K..', '..K.' ],
[ '.K..', 'K...', '...K', 'K...' ],
[ '.K..', 'K...', '...K', '..K.' ],
[ '.K..', 'K...', '...K', '...K' ],
[ '.K..', '.K..', '.K..', '.K..' ],
[ '.K..', '..K.', '.K..', 'K...' ],
[ '.K..', '..K.', '.K..', '..K.' ],
[ '.K..', '..K.', '...K', 'K...' ],
[ '.K..', '..K.', '...K', '..K.' ],
[ '..K.', '.K..', 'K...', '.K..' ],
[ '..K.', '.K..', 'K...', '...K' ],
[ '..K.', '.K..', '..K.', '.K..' ],
[ '..K.', '.K..', '..K.', '...K' ],
[ '..K.', '..K.', '..K.', '..K.' ],
[ '..K.', '...K', 'K...', 'K...' ],
[ '..K.', '...K', 'K...', '.K..' ],
[ '..K.', '...K', 'K...', '...K' ],
[ '..K.', '...K', '..K.', '.K..' ],
[ '..K.', '...K', '..K.', '...K' ],
[ '...K', 'K...', 'K...', 'K...' ],
[ '...K', 'K...', 'K...', '...K' ],
[ '...K', 'K...', '.K..', 'K...' ],
[ '...K', 'K...', '.K..', '..K.' ],
[ '...K', 'K...', '...K', 'K...' ],
[ '...K', 'K...', '...K', '..K.' ],
[ '...K', 'K...', '...K', '...K' ],
[ '...K', '..K.', '.K..', 'K...' ],
[ '...K', '..K.', '.K..', '..K.' ],
[ '...K', '..K.', '...K', 'K...' ],
[ '...K', '..K.', '...K', '..K.' ],
[ '...K', '...K', 'K...', 'K...' ],
[ '...K', '...K', 'K...', '.K..' ],
[ '...K', '...K', 'K...', '...K' ],
[ '...K', '...K', '...K', 'K...' ],
[ '...K', '...K', '...K', '...K' ]
]
*/
'Algorithm&Data structure > JS alg.' 카테고리의 다른 글
다익스트라(Dijkstra) 알고리즘 (0) | 2024.12.14 |
---|---|
Brute force 알고리즘 +NP문제 (0) | 2024.11.11 |
탐욕법 (greedy algorithm) (1) | 2024.11.09 |
동적 프로그래밍(Dynamic Programming) (0) | 2024.11.08 |
최소신장트리(Minimum Spanning Tree, MST) + (프림, 크루스칼 알고리즘) (0) | 2024.11.05 |