링크

문제 링크

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

입출력 예

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

풀이

1. 어차피 퀸은 같은 row에는 오지 못한다. col이라는 1차원 배열을 통해서, (i, col[i])가 퀸이 놓인 좌표가 되게하자.
2. 백트래킹을 할 때, 퀸을 거기가 둘 수 있는지 check를 한다.
3. check는 같은 컬럼에 이미 퀸이 있는지, 왼쪽 대각선에 퀸이 있는지, 오른쪽 대각선에 퀸이 있는지를 판단하고 모두 통과했으면 true를 반환하게 한다.

아주 유명하고 대표적인 백트래킹 문젠데 구현력이 딸려서 도움을 얻은곳에서 코드를 그냥 봤다.

처음에 2차원 배열을 놓고 푸는게 맞는 줄 알고 놓고 했다가 도대체가 대각선에 놓인 퀸의 여부를 찾다가 구현하는 걸 포기했다. 어려워서가 아니라 코드가 너무 지저분해져서... 도저히 이 방식은 아닌 것 같았다...

그래서 좌표들을 나열해놓고 보니 규칙을 찾게 되었고, 아이디어 접근은 제대로 했으나 구현력이 딸렸던 것 같다 ㅜ 아직 멀었다..

코드

import java.util.*;
class Solution {
    static int[] col;
    public boolean check(int here) {
        for(int i = 0; i < here; i++) {
            if(col[here] == col[i]) return false;
            if(Math.abs(col[here] - col[i]) == here - i) return false;
        }
        return true;
    }
    public int dfs(int n, int index) {
        if(index == n) {
            return 1;
        }
        int res = 0;
        for(int i = 0; i < n; i++) {
            col[index] = i;
            if(check(index)) res += dfs(n, index + 1);
            col[index] = -1;
        }
        return res;
    }
    public int solution(int n) {
        int answer = 0;
        col = new int[n];
        for(int i = 0; i < n; col[i++] = -1);
        answer = dfs(n, 0);
        return answer;
    }
}