99클럽 코테 스터디 16일차 TIL

오늘의 학습 키워드

• 백트래킹 (Backtracking)
• N-Queen 문제

문제 이해

N-Queen 문제는 N x N 크기의 체스판 위에 N개의 퀸을 서로 공격하지 못하도록 배치하는 방법의 수를 구하는 문제입니다. 퀸은 같은 행, 열, 대각선에 위치한 다른 퀸을 공격할 수 있기 때문에 이를 피하면서 배치를 찾아야 합니다.

나의 풀이

class Solution {
    int N;
    int[] visited; 
    int answer = 0;
    public int solution(int n) {
        N = n;
        visited = new int[N];
        dfs(0);
        return answer;
    }
    public void dfs(int checked){
         if (checked == N){
            answer++;
            return;
        }
        for (int i = 0; i < N; i++) {
            if (canCheck(checked, i)){
                visited[checked] = i;
                dfs(checked + 1);
            }
        }
    }

    public boolean canCheck(int row, int col){
         for (int i = 0; i < row; i++) {
            if(visited[i] == col){ //가로 확인
                return false;
            }else if(Math.abs(row - i) == Math.abs(col - visited[i])){ //대각선 확인
                return false;
            }
        }
        return true;
    }
}

풀이 설명

1. 초기화

   • N은 체스판의 크기이자, 퀸의 수를 의미합니다. 이 변수는 입력값 n으로 초기화됩니다.
   • visited 배열은 각 행에 퀸이 배치된 열의 위치를 기록합니다.
   • answer는 가능한 퀸 배치의 수를 기록합니다.

2. 백트래킹을 통한 퀸 배치

   • dfs 메소드는 퀸을 배치할 수 있는 모든 방법을 탐색합니다.
   • checked는 현재까지 배치한 퀸의 수를 의미합니다. 만약 checked가 N에 도달하면, 하나의 유효한 배치가 완성된 것으로 간주하고 answer를 증가시킵니다.
   • 각 행에서 가능한 모든 열을 검사하여 퀸을 배치합니다. 퀸을 배치할 수 있는지 여부는 canCheck 메소드로 판단합니다.

3. 퀸 배치 가능 여부 확인

   • canCheck 메소드는 주어진 행(row)에 퀸을 배치할 수 있는지 확인합니다.
   • 이미 같은 열에 퀸이 있는지, 또는 대각선으로 퀸이 배치되어 있는지를 검사하여 불가능한 경우 false를 반환합니다. 이 두 조건을 모두 통과하면 true를 반환하여 해당 위치에 퀸을 배치할 수 있음을 알립니다.

4. 결과 반환

   • 모든 가능한 퀸 배치를 탐색한 후, answer에 기록된 퀸 배치의 수를 반환합니다.

오늘의 회고

• dfs를 이용한 백트래킹 문제였다.