글 읽기 - N-Queen 코드에서 이해가 안되는 부분이 있어요

dyed4eyes 6년 전 0

check_dig1, check_dig2 가 row+col, row+N-col 인덱스를 사용가능 하게 하는 원리가 잘 이해가 안됩니다.

또 check(row,col)를 한 다음 check_col, check_dig1, check_dig2 를 방문으로 바꾸고 dfs 탐색을 하는 이유도 헷갈리네요.

이 두 가지에 대해 답변해주실 분 계신가요?

import java.util.Scanner;

public class Main {

	static boolean[] check_col = new boolean[15];
	static boolean[] check_dig1 = new boolean[40];
	static boolean[] check_dig2 = new boolean[40];
	static int N;
	
	static int dfs(int row){
		if(row == N) return 1;
		int ans=0;
		for(int col=0; col<N; col++){
			if(check(row,col)){
				check_col[col] = true;
				check_dig1[row+col] = true;
				check_dig2[row+N-col] = true;
				ans += dfs(row+1);
				check_col[col] = false;
				check_dig1[row+col] = false;
				check_dig2[row+N-col] = false;
			}
		}
		return ans;
	}
	
	static boolean check(int row, int col){
		if(check_col[col])
			return false;
		if(check_dig1[row+col])
			return false;
		if(check_dig2[row+N-col])
			return false;
		return true;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		System.out.println(dfs(0));
	}
}

sgchoi5 6년 전 1

http://gooddaytocode.blogspot.kr/search/label/%5B001%5D%20알고리즘%20공부%20시작하기%20좋은%20조합

요기에 소개하는 책에 좋은 설명이 있습니다.... : )

dyed4eyes 6년 전 0

생각해보니 row+col 을 하면 우상대각이 같은 값을 갖는군요. row+N-col 을 하면 좌상 대각이 같은 값을 갖구요. 그래서 1차원 boolean 배열로 각 대각선에 대한 퀸 존재 여부를 검사 할 수 있게 되네요.

그렇기에 check(row,col)를 한 다음에 퀸을 놓는 방식으로 해결되는거구요.

sgchoi5 님 답변 감사해요 :)

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

문제

문제

출처

ICPC

N-Queen 코드에서 이해가 안되는 부분이 있어요

dyed4eyes 6년 전 0

sgchoi5 6년 전 1

dyed4eyes 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말