[SWEA] 2806 : N-Queen

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=JAVA&select-1=3&pageSize=10&pageIndex=2 

SW Expert Academy

그동안 푼 것처럼 DFS 재귀로 풀었는데 시간이 너무 많이 나왔다. 그래서 다른 사람들 코드 가져옴.

 

내 코드

메모리 : 20232 KB

시간 : 2036 ms

코드길이 : 1684 B

 

[내 코드]

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

public class Solution {
	static int N;
	static int result;
	//현재상하좌우대각선4
	static int[] dir_x = {-1, 1, 0, 0, -1, -1, 1, 1};
	static int[] dir_y = {0, 0, -1, 1, -1, 1, -1, 1};

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			sb.append('#').append(t).append(' ');
			N = Integer.parseInt(br.readLine());
			boolean[][] isVisit = new boolean[N][N];
			result = 0;
			
			if(N == 1) {
				sb.append(1).append('\n');
				continue;
			}
			
			for(int r = 0; r < N; r++) {
				for(int c = 0; c < N; c++) {
					isVisit[r][c] = true;
					putQueen(r, c, isVisit, 1);
					isVisit[r][c] = false;
				}
			}
			
			sb.append(result).append('\n');
		}
		System.out.print(sb);
	}
	
	static void putQueen(int row, int column, boolean[][] isVisit, int queen) {
		//공격 방향에 다른 퀸이 있으면 return
		for(int i = 0; i < 8; i++) {
			int nowRow = row + dir_x[i];
			int nowColumn = column + dir_y[i];
			while(nowRow >= 0 && nowRow < N && nowColumn >= 0 && nowColumn < N) {
				if(isVisit[nowRow][nowColumn])
					return;
				nowRow += dir_x[i];
				nowColumn += dir_y[i];
			}
		}

		if(queen == N) {
			result++;
			return;
		}
		
		for(int r = row + 1; r < N; r++) {
			for(int c = 0; c < N; c++) {
				if(!isVisit[r][c] && r != row && c != column) {
					isVisit[r][c] = true;
					putQueen(r, c, isVisit, queen + 1);
					isVisit[r][c] = false;
				}
			}
		}		
		return;
	}
}

 

[1]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Solution {
    public static int[] row;
    public static int TC, a, b, lineCounter, count;
 
    public static boolean place(int r, int c) {
        for (int prev = 0; prev < c; prev++) {
            if (row[prev] == r || Math.abs(row[prev] - r) == Math.abs(prev - c))
                return false;
 
        }
        return true;
    }
 
    public static void backtrack(int N, int c) {
        if (c == N) {
            count++;
        }
        for (int r = 0; r < N; r++) {
            if (place(r, c)) {
                row[c] = r;
                backtrack(N, c + 1);
            }
        }
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
 
        for (int z = 1; z <= T; z++) {
            int N = Integer.parseInt(br.readLine());
            row = new int[N];
            count = 0;
            backtrack(N, 0);
            System.out.println("#" + z + " " + count);
 
        }
 
    }
 
}

[2]

import java.util.Scanner;
 
class Solution
{
    static int N;
    static int[] board;
    static int result;
     
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
 
        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = sc.nextInt();
 
            board = new int[N];
            result = 0;
             
            queen(0);
             
            System.out.println("#" + test_case + " " + result);
        }
    }
     
    public static void queen(int y) {  
        if (N == y) {
            result++;
            return;
        }
         
        for (int i = 0; i < N; i++) {
            board[y] = i;
            if (check(y)) {
                queen(y + 1);
            }
        }
    }
     
    static boolean check(int y) {
        for (int i = 0; i < y; i++) {
            if (board[y] == board[i] || y - i == Math.abs(board[y] - board[i])) {
                return false;
            }
        }
        return true;
    }
}