글 읽기 - 고수님들 N-Queen문제 시간초과좀 봐주세요

hankim0627 5년 전 0

2차원 배열로 만들었다가 시간초과가 떠서

1차원 배열로 만들었는데도 역시 시간초과가 뜹니다ㅜㅜ

import java.util.Scanner;

public class BOJ9663 {
	public static int N;
	public static int[] chess;
	public static int ans = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		chess = new int[N*N];
		for(int i = 0; i < N; i++){
			dfs(i*N,0);
		}
		System.out.println(ans);
	}
	
	private static void dfs(int x, int cnt){
		chess[x] = 1;
		cnt++;
		
		if(cnt == N){
			ans++;
			--cnt;
			chess[x] = 0;
			return;
		}
		
		for(int i = 0; i < N; i++){
			if (chess[((x/N+1)*N+i)%(N*N)] != 1) {
                //다음 행의 모든 열 체크
				if (isPromise(((x/N+1)*N+i)%(N*N))) {
					dfs(((x/N+1)*N+i)%(N*N), cnt);
				}
			}
		}//for-i-end
		--cnt;
		chess[x] = 0;
		return;
	}//dfs-end
	
	private static boolean isPromise(int x){
		int tempRow = x/N;
		int tempCol = x%N;

		for(int i = tempCol; i < N*N; i=i+N){
			if(chess[i] == 1){	//같은 열 검사
				return false;
			}
		}
		for(int i = 0; i < N*N; i++){
			if(Math.abs(tempRow - i/N) == Math.abs(tempCol - i%N)){
				if(chess[i] == 1){
					return false;					
				}
			}
		}
		return true;
	}
}

djm03178 5년 전 1

매번 검사를 하기 위해 모든 열과 모든 행과 모든 대각선을 탐색하지 말고, 각각을 O(1)에 해결할 수 있는 방법을 생각해 보세요.

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

문제

문제

출처

ICPC

고수님들 N-Queen문제 시간초과좀 봐주세요

hankim0627 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말