글 읽기 - n-queen 질문

qotnals1320 4년 전 0

체스판 첫째행을 기준으로 dfs탐색을 통해서 개수를 구하려고 하였는데 답이 맞지 않지만 틀릴만한 부분이 어디에 생기는지 잘 모르겠어서

질문드립니다.

import java.util.*;
import java.io.*;
public class Main{
	
	static boolean[][] check;
	static int[][] arr;
	static int n;
	static int cnt;
	
	public static void main(String args[]) throws IOException{
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		check = new boolean[n][n];
		arr = new int[n][n];
		cnt = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				Arrays.fill(check[j], false);
			}
			check[0][i] = true;
			dfs();
			
		}
		System.out.print(cnt);
	}
	static void dfs() {
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(check[i][j]==false && isPossible(i, j)) {
					check[i][j] = true;
					cnt++;
					dfs();
				}
			}
		}
	}
	static boolean isPossible(int x, int y) {
		for(int i=0;i<n;i++) {
			if(check[i][y]==true) return false;
			if(check[x][i]==true) return false;
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(Math.abs(i-x)==Math.abs(j-y)) {
				if(check[i][j]==true) return false;
				}
			}
		}
		return true;
	}
	
}

iamkkwak 4년 전 1

DFS에서 check를 다시 false로 바꿔주는 부분이 없는 것 같은데요??

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

n-queen 질문

qotnals1320 4년 전 0

iamkkwak 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말