9663번 N-Queen

링크 : https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

---

 

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

예제 입력 1

8

예제 출력 1 

92

 

---

구현 방법

1) for문을 통해 첫자리에 queen을 놓고 dfs를 통해 다음 행의 queen자리르 찾음

2) 이때 방금 전에 놓은 퀸의 위치가 유망한지 검사하여 유망하지 않다면 return, 유망하다면 dfs계속 진행

3) 만약 N개의 queen을 다 놓았다면 경우의 수 증가

 

 

구현 코드

import java.io.*;
import java.util.*;
public class Main {
	static int count;
	static int[] col;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		col = new int[N+1];
		count = 0;
		dfs(N,1);
		System.out.println(count);
	}
	public static void dfs(int N, int cnt) {
		if(!checking(N,cnt-1)) return;
		if(cnt>N) {
			count++;
			return;
		}
		for(int i=1; i<=N; i++) {
			col[cnt] = i;
			dfs(N, cnt+1);
		}
	}
	public static boolean checking(int N, int cnt) {
		//같은 열 아님
		//대각선 관계 아님
		for(int i =1; i<cnt; i++) {
			if(col[i]==col[cnt] ||
					Math.abs(col[cnt]-col[i])==cnt-i) return false;
		}
		return true;
	}
}

 

---

다른 사람의 풀이참조

위의 코드는 다음 자리에 퀸을 두고, 그 다음 연산에서 방금 전에 놓은 퀸이 유망한지 보는 코드였다면, 이 블로그 코드는 퀸을 놓기 전, 유망한 자리라면 퀸을 놓고 그렇지 않다면 퀸을 놓지 않는다.

https://chanhuiseok.github.io/posts/baek-1/

[백준] 9663번 - N-Queen