중요하거나 어려웠던 문제에 대해 작성합니다.
- 백트래킹 필수문제
문제 📝
사실상 백트레킹 필수 문제로, 아마 실제로 이 문제를 처음 접했다면 체감 난이도는 좀 더 높을 것이다. 문제의 경우 다음 링크를 클릭하면 된다.
해결 💡
백트레킹(Backtracking)
백트래킹 위키피디아
주요 개념은 해를 얻을 때까지 모든 가능성을 조사하는 것이다. 데이터로 트리를 구성하여 이를 검사하기 위해 깊이 우선 탐색(Depth-First Search, DFS) 을 사용한다. 탐색 중에 오답을 만나면 이전 분기점으로 돌아간다. 시도해보지 않은 다른 해결 방법이 있으면 시도한다. 해결 방법이 더 없으면 더 이전의 분기점으로 돌아간다.
백트래킹의 Pseudocode는 아래와 같다.
1. reject(P,c): 만약 다음의 노드가 후보가 아닌다면 return으로 끝낸다.
2. accept(P,c): 만약 현재 노드까지가 답과 일치한다면 답을 출력한다.
3. first(P,c): 후보 C의 첫번째 확장을 시작한다.
4. 답이 없을때까지 다음 함수를 계속 반복한다.
procedure backtrack(P, c) is
if reject(P, c) then return
if accept(P, c) then output(P, c)
s ← first(P, c)
while s ≠ NULL do
backtrack(P, s)
s ← next(P, s)해설
기본적으로 각 열마다 단계를 구성하며, DFS를 진행할 dfs(), 단계가 내려갈 때마다 해당 열에 퀸을 놓을 수 있는지 확인하는 isValid()가 필요하다.
보통 DFS 문제를 해결할 때, 데이터와 더불어 방문visited을 체크한다. 방문을 했으면 재방문하지 않는다는 것을 지키기 위함이다. 여기서 방문 배열의 목적은 인덱스에 해당하는 열에 퀸을 놓았는지 확인하기 위한 목적이다. 즉, 탐색을 하면서 해당 열을 방문했는지 확인하면서 방문하였으면 그 열을 제외한다.
(물론, isValid() 내부에 조건식을 추가하여 visited를 사용하지 않는 방법도 존재한다.)
우선, 행 row가 끝까지 닿고 최종적으로 모든 퀸이 채워질 때, 행이 하나씩 더해지다보면 결국 row == N 까지 오게 되는데, 이때가 정답 중 하나의 후보이므로 최종 정답에 1을 더해준다.
그리고 놓을 수 있는 조건을 찾아 isValid()에 적용한다. 퀸이 공격할 수 있는 모든 방법을 찾아서 공격 가능시 false 불가능 시 true 를 반환한다.
기본적으로 퀸은 가로(행), 세로(열), 대각선 공격이 가능하다. 가로 공격은 각 행에 퀸을 하나씩 놓는 것으로 해결 가능하고, 세로는 visited를 활용하서 해결하였다. 대각선만 해결하면 된다.
임의의 퀸에 대해서 그 퀸과의 가로 거리와 세로 거리가 같을 경우 대각선 방향에 있게 된다. 현재 놓는 퀸의 위치가 (행, 열) 기준 (row, col), 다른 퀸은 (oldRow, oldCol) 일 때 다음을 만족하면 대각선 공격이 가능하다.
abs(row - oldRow) == abs(col - oldCol) 그리고 dfs()에서 isValid() == true 일 시에 방문 처리 해주고 탐색을 완료하면 방문 처리를 해제함을 잊지 말자.
Python 🐍
def dfs(row):
global ans
if(row == n):
ans += 1
return
for col in range(n):
if(isValid(row, col)):
column[row] = col
visited[col] = True
dfs(row + 1)
visited[col] = False
def isValid(row, col):
if(visited[col]):
return False
for oldRow in range(row):
oldCol = column[oldRow]
if(abs(row - oldRow) == abs(col - oldCol)):
return False
return True
n = int(input())
ans = 0
column = [0 for i in range(N)]
visited = [False for i in range(N)]
dfs(0)
print(ans)Java ☕️
import java.util.Scanner;
public class Main {
static int n, ans;
static int[] column;
static boolean[] visited;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
column = new int[n];
visited = new boolean[n];
dfs(0);
System.out.println(ans);
sc.close();
}
private static void dfs(int row) {
if(row == n) {
ans++;
return;
}
for(int col = 0; col < n; col++) {
if(isValid(row, col)) {
column[row] = col;
visited[col] = true;
dfs(row + 1);
visited[col] = false;
}
}
}
private static boolean isValid(int row, int col) {
if(visited[col]) {
return false;
}
for(int oldRow = 0; oldRow < row; oldRow++) {
int oldCol = column[oldRow];
if(Math.abs(row - oldRow) == Math.abs(col - oldCol)) {
return false;
}
}
return true;
}
}
