공부 222일차: 백준 9663번 N-Queen 자바 java

9663 N-Queen

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

9663번: N-Queen

 

 

 

 

---

백준 9663번 문제 N-Queen

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
10 초	128 MB	86866	41771	27108	46.790%

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

제한

 

예제 입력 1

8

예제 출력 1

92

힌트

 

 

 

---

과정 생각해보기 & 오답

---

 

체스 규칙을 몰라서, 퀸끼리 서로 공격할 수 없게 만드는 조건이 무엇인지 알아야 했다

이 기사를 확인해 보니 각각 다른 가로줄, 세로줄, 대각선에 있어야 한다는 게 조건이다

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    static int n, cnt;
    static int[][] board;
    static boolean[][] visited;
    static int[] dx = {-1, -1, 1, 1};
    static int[] dy = {-1, 1, -1, 1};
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        visited = new boolean[n][n];
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                visited = new boolean[n][n];     // 초기화
                dfs(0, i, j);
            }
        }
        
        bw.write(cnt+"");
        bw.flush();
        bw.close();
        br.close();
    }
 
    static void dfs(int depth, int x, int y) {
        if(depth == n) {    // 끝까지 다 돌다 == 경우의 수 중 하나
            cnt++;
            return;
        }
 
        board[x][y] = 1;    // 퀸 표시
        
        // 같은 가로줄, 세로줄 방문 불가
        for(int i = 0; i < n; i++) {
            visited[x][i] = true;
            visited[i][y] = true;
        }
        
        // 대각선 방문 불가
        for(int i = 0; i < 4; i++) {
            int X = x+dx[i];
            int Y = y+dy[i];
            
            if(X < 0 || X > n-1 || Y < 0 || Y > n-1) {
                continue;
            }
            
            visited[X][Y] = true;
        }
        
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < n; j++) {
                int X = x+i;
                int Y = y+j;
                
                // 범위 밖
                if(X < 0 || X > n-1 || Y < 0 || Y > n-1) {
                    continue;
                }
                
                
                if(!visited[X][Y]) {
                    board[X][Y] = 1;    // 퀸 표시
                    dfs(depth+1, X, Y);
                }
            }
        }
    }
}
 

인접한 대각선들만 피하면 되는 걸로 착각해서 썼다가 틀린 코드. 물론 그것 말고도 문제가 많다

 

열의 차와 행의 차가 같으면 같은 대각선에 있는 것이다

아래 표로 보자

0,0	0,1	0,2	0,3
1,0	1,1	1,2	1,3
2,0	2,1	2,2	2,3
3,0	3,1	3,2	3,3

빨간 색깔로 표시한 부분이 대각선인데, 행과 열의 차의 절댓값이 모두 1임을 알 수 있다

대각선이 아닌 파란 색깔은 1,2와 비교했을 때 차의 절댓값이 각각 0, 1이 나온다 

 

 

 

---

정답 인정 코드

---

 

1. 1차원 배열 이용 (이 블로그 참고)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    static int n, cnt;
    static int[] arr;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        
        dfs(0);
        bw.write(cnt+"");
        bw.flush();
        bw.close();
        br.close();
    }
 
    static void dfs(int depth) {
        if(depth == n) {    // 끝까지 다 돌다 == 경우의 수 중 하나
            cnt++;
            return;
        }
 
        for(int i = 0; i < n; i++) {
            arr[depth] = i;
            
            if(isPossible(depth)) {
                dfs(depth+1);
            }
        }
    }
    
    static boolean isPossible(int col) {
        for(int i = 0; i < col; i++) {
            if(arr[col] == arr[i]) {    // 같은 행
                return false;
            }else if(Math.abs(col-i) == Math.abs(arr[col]-arr[i])) {    // 대각선
                return false;
            }
        }
        
        return true;
    }
}
 

훨씬 간단

 

2. 2차원 배열 이용

 

 

 

---

1차원 배열로 풀다니 이런 걸 어떻게 생각하지?!

그래도 2차원 배열로도 풀어보고 싶어서 나중에 재도전 예정..