[백준] 9663번 : N-Queen - 자바[Java]

https://www.acmicpc.net/problem/9663

문제

대표적인 백트래킹 문제다.

완전탐색/DFS와 비슷하지만, '정답이 될 수 없다면 다시 돌아오는 과정' = 가지치기를 한다.

즉, 불필요한 경로는 끝까지 탐색하지 않는다.

 

백트래킹의 개념과 문제 모음

 

풀이

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

public class Main {

    static int n;
    static boolean[][] board;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(br.readLine());
        board = new boolean[n][n];

        backtraking(0);

        System.out.println(count);
    }

    static void backtraking(int row) {
        if (row == n) {
            count++;
            return;
        }

        for (int i = 0; i < n; i++) { // row번째 줄에 퀸을 놓기
            if (check(row, i)) {
                board[row][i] = true;
                backtraking(row+1);
                board[row][i] = false;
            }
        }
    }

    static boolean check(int row, int col) {
        // 해당 열에 퀸이 놓여있는지 검사
        for (int i = 0; i < n; i++) {
            if (board[i][col]) {
                return false;
            }
        }

        // 대각선
        // 우상단
        int i = row-1;
        int j = col+1;
        for (; i >= 0 && j < n; i--, j++) {
            if (board[i][j]) {
                return false;
            }
        }
        // 우하단
        i = row;
        j = col;
        for (; i < n && j < n; i++, j++) {
            if (board[i][j]) {
                return false;
            }
        }
        // 좌상단
        i = row;
        j = col;
        for (; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j]) {
                return false;
            }
        }
        // 좌하단
        i = row;
        j = col;
        for (; i < n && j >= 0; i++, j--) {
            if (board[i][j]) {
                return false;
            }
        }

        return true;
    }
}

수정한 풀이

• 0번째 줄에는 무조건 퀸을 놓아야 하기 때문에 backtracking(1)부터 시작한다.
• 0번째 줄부터 아래줄로 이동하면서 놓기 때문에, 하단에 퀸이 있는지는 검사할 필요가 없다.

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

public class Main {

    static int n;
    static boolean[][] board;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(br.readLine());
        board = new boolean[n][n];

        for (int i = 0; i < n; i++) { // 0번째 줄에 퀸을 놓기
            board[0][i] = true;
            backtraking(1);
            board[0][i] = false;
        }

        System.out.println(count);
    }

    static void backtraking(int row) {
        if (row == n) {
            count++;
            return;
        }

        for (int i = 0; i < n; i++) { // row번째 줄에 퀸을 놓기
            if (check(row, i)) {
                board[row][i] = true;
                backtraking(row+1);
                board[row][i] = false;
            }
        }
    }

    static boolean check(int row, int col) {
        // 해당 열에 퀸이 놓여있는지 검사
        for (int i = 0; i < n; i++) {
            if (board[i][col]) {
                return false;
            }
        }

        // 대각선

        // 우상단
        int i = row-1;
        int j = col+1;
        for (; i >= 0 && j < n; i--, j++) {
            if (board[i][j]) {
                return false;
            }
        }
        // 좌상단
        i = row-1;
        j = col-1;
        for (; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j]) {
                return false;
            }
        }

        return true;
    }
}

다음과 같이 한꺼번에 체크하는 것도 가능하다.

아래는 2차원 배열이 아닌 1차원 배열을 사용한다. 각 원소의 index를 '열'이라 생각하고, 원소 값을 '행'이라 생각하는 것이다.

	private static boolean check(int r, int c) {
		// 같은 열, 위쪽 대각선에 퀸이 있는지 확인
		for (int i = 0; i < r; i++) {
			if (queen[i] == c || r - i == c - queen[i] || r - i == queen[i] - c) {
				return false;
			}
			
		}
		
		return true;
	}

이전 풀이

백준 9663 N-Queen[Java]