[레이튼 교수와 이상한 마을] 체스판의 퀸1을 알고리즘으로 풀어보자.

 

[레이튼 교수와 이상한 마을]

요즘 재밌게 하고 있는 게임이다.

내가 진짜 탐정이 된 기분...(?)으로 퀴즈 하나하나 풀어가는데 진짜진짜 재밌다.

 

 

 

 

그러다가 나온 문제..

 

 

 

 

"허어어엉ㅇㄱ!!! 아니 이거 N Queen 문제잖아!!"

참고)

https://2un-light.tistory.com/84

 

 

 

공부했던 문제가 나와서 반가운 마음에, 이 문제를 알고리즘으로 다시 풀어보려고 한다. ^^

이전에는 경우의 수를 카운트 하는 풀이였다면, 이번에는 친절히 퀸을 어디두면 좋을지 출력도 해주자~👻

 

 

💡문제풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class NQueen {
    static int N; //체스판의 크기 (N X N)
    static boolean[] cols, leftDiagonals, rightDiagonals; //열, 대각선 체크
    static int[] board; //체스판 : 각 행에서 퀸이 위치한 열 저장


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("체스판의 칸 수를 입력해 주세요.");
        System.out.println("예시) 4 -> 4 X 4 체스판");
        N = Integer.parseInt(br.readLine());

        //방문 여부 체크 배열 초기화
        cols = new boolean[N];
        leftDiagonals = new boolean[2 * N - 1]; //왼쪽 대각선 방향 \
        rightDiagonals = new boolean[2 * N - 1]; // 오른쪽 대각선 방향 /
        board = new int[N];

        //백트래킹 시작
        solve(0);
    }

    public static void solve(int row) {
        if(row == N) {
            pringBoard();
            return;
        }

        for(int col = 0; col < N; col++){
            if(isValid(row, col)) {
                placeQueen(row, col, true); //퀸 배치
                board[row] = col; //현재 행에 퀸 위치 저장
                solve(row + 1); //다음 행으로 이동
                placeQueen(row, col, false); //원상복구
            }
        }
    }

    //유효성 검사 : 같은 열, 대각선에 퀸이 있는지 확인
    public static boolean isValid(int row, int col) {
        return !cols[col] && !leftDiagonals[row - col + N - 1] && !rightDiagonals[row + col];
    }

    public static void placeQueen(int row, int col, boolean isPlacing) {
        cols[col] = isPlacing;
        leftDiagonals[row - col + N - 1] = isPlacing;
        rightDiagonals[row + col] = isPlacing;
    }

    public static void pringBoard() {
        for(int i = 0; i < N; i++) {
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < N; j++) {
                if(board[i] == j) sb.append("👑 ");
                else sb.append(". ");
            }
            System.out.println(sb.toString());
        }
        System.out.println();
    }
}

 

1. 왼쪽 대각선 (↘ 방향 )

수식: row - col

• 왼쪽 대각선에 있는 좌표들은 row - col이 항상 일정한 값을 가짐
• 예를 들어, (0,0) → (1,1) → (2,2) → (3,3)은 모두 row - col = 0
• (1,0) → (2,1) → (3,2)는 row - col = 1

배열 인덱스로 변환하는 이유

row - col 값이 음수가 될 수도 있으므로, 배열의 인덱스로 변환하기 위해 N - 1을 더해줌
👉 수식: leftDiagonals[row - col + (N - 1)]

---

2. 오른쪽 대각선 (↙ 방향)

수식: row + col

• 오른쪽 대각선에 있는 좌표들은 row + col이 일정한 값을 가짐
• 예를 들어, (0,3) → (1,2) → (2,1) → (3,0)은 모두 row + col = 3
• (0,2) → (1,1) → (2,0)은 row + col = 2

👉 수식: rightDiagonals[row + col]
이 값은 항상 0 이상이므로 따로 변환할 필요 없음.

 

 

✅ 결과

 

 

 

히히 이제 N Queen 문제가 또 나오면 

이 프로그램에 숫자를 입력하면 간단하게 해결할 수 있다 !