[SWEA 2806번] N-Queen

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE&problemTitle=queen&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&&

SW Expert Academy

import java.io.*;
import java.util.*;

public class Solution {

    static int[] board;

    static int result;

    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        for (int test = 1; test < T + 1; test++) {
            N = Integer.parseInt(br.readLine());
            result = 0;
            board = new int[N];
            dfs(0);
            System.out.println("#"+test+" "+result);

        }
    }

    private static void dfs(int queen) {
        if (queen == N) {
            result++;
            return;
        }

        for (int i = 0; i < N; i++) {
            board[queen] = i;
            if(solution(queen)){
                dfs(queen+1);
            }
        }
    }

    private static boolean solution(int col) {
        for(int i=0; i<col; i++){
            // 직선
            if(board[col] == board[i]){
                return false;
            }
            // 대각선
            else if(Math.abs(col-i) == Math.abs(board[col]- board[i])){
                return false;
            }
        }
        return true;
    }


}

 

와 진짜 어렵다... 백준이랑 똑같은 문제가 있어서 티어를 봤는데 골드4... 

 

이 문제는 board 배열을 일차원적으로 생각하면 쉽게 접근할 수 있다. 먼저 DFS를 통해 현재 놓인 퀸의 수를 받아오고, 그다음 solution 함수를 호출해 직선이나 대각선에 이미 다른 퀸이 존재하는지를 판단한다. 만약 충돌이 없다면 true를 반환해 다음 단계로 진행하며, 이런 방식으로 반복하며 문제를 해결한다.

 

즉 board[0]=1 이면 0,1을 뜻한다. 이때 일반 배열 기준이랑 다르게 1번째 줄에 2번째 값을 1이다 라는것이다!

이 문제는 글로 이해하는 것보다, 실제 코드를 보면서 직접 해석해보는 것을 추천한다!