SWEA D3 2806 NQueen

SWEA D3 2806 NQueen

 

 

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB

SW Expert Academy

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=IupKey2970I

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package se.code.d3;

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

/**
 * @author itsmeyjc
 * @since 2019. 3. 7.
 * @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB
 * @mem 29,264 kb
 * @time 127 ms
 * @caution #backtracking, #dfs
 */
public class SWEA_D3_2806_NQueen {
    static StringBuilder output = new StringBuilder();

    static int T;
    static int N;
    static int[] columnOf;// 각 row를 index로 해당 row에서의 column 값을 저장할 배열
    static int answer;

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

        T = Integer.parseInt(input.readLine());

        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(input.readLine());

            columnOf = new int[N];
            answer = 0;
            dfs(0);

            output.append("#").append(t).append(" ").append(answer).append("\n");
        }
        System.out.println(output);
    }

    static void dfs(int row) {
        if (row == N) {
            answer++;
            return;
        }
        for (int col = 0; col < N; col++) {
            columnOf[row] = col;
            // 방금 놓은 자리가 유망하다면 다음 가보기
            if (isPromising(row)) {
                dfs(row + 1);
            }
        }
    }

    static boolean isPromising(int currentRow) {
        for (int r = 0; r < currentRow; r++) {
            // 위쪽으로 혹시 같은 값 없나?
            if (columnOf[r] == columnOf[currentRow]) {
                return false;
            }
            // 오른쪽, 왼쪽 대각선으로 위쪽으로 가면서 같은 녀석 없나?
            if (Math.abs(r - currentRow) == Math.abs(columnOf[r] - columnOf[currentRow])) {
                return false;
            }
        }
        return true;
    }
    // END:

    static String src = "2\r\n" +
                        "1\r\n" +
                        "2";
}