[백준] 9663 - N-Queen (JAVA)

1. 소요시간 : 30분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 4
4. 문제 유형 : 브루트포스 알고리즘, 백트래킹
5. 다른 사람의 풀이를 참고 했는가 ? : O
6. 한 번 풀었다가 다시 푸는 문제인가 ? : O
7. 문제 링크 : https://www.acmicpc.net/problem/9663
8. 푼 날짜 : 2023.03.18

1. 사용한 자료구조 & 알고리즘

백트래킹을 사용했다.

2. 사고과정

우선 다시 푸는 문제이기에 행, 열에 어떻게 접근해줘야 하는지는 이전에 remind 한 것으로 잘 알고 있었다. 하지만 두 가지에서 막혔는데,
dfs를 다시 실행할 떄의 조건과
대각선 체크를 어떻게 해주는지에 대해서다.

두 방법의 solution 을 찾기 위해서 다른 사람의 풀이는 아니고 내가 전에 제출했던 코드를 다시 살펴 봤다. (이전에 제출한 것이 다른 사람의 풀이를 참고한 코드이니 사실상 다를 것은 없다.)

20분 정도 보고 2가지를 해결하지 못해서 풀이를 참고 했고, 10분 동안 다시 이해를 하고 문제를 풀었다.

3. 풀이과정

1. i를 행, map[i]를 열로 본다.
2. 우선 행에 퀸을 놓는다.
3. 다음에 퀸을 놓은 위치가 퀸을 놓아도 되는 위치였는지 check 하고, true 라면 depth를 1 증가시켜서 탐색한다.
4. 깊이가 map의 길이만큼 갔다면 count 를 증가한다.

4. 소스코드

import java.io.*;
import java.util.*;

public class Main {
	
	static int map[];
	static int count=0;
	
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n=Integer.parseInt(br.readLine());
		map=new int[n];
		dfs(0);
		System.out.println(count);
		
		
	}
	public static void dfs(int depth) {
		if(depth==map.length) {
			count++;
			return;
		}
		for(int i=0;i<map.length;i++) {
			map[depth]=i;
			if(check(depth)) {
				dfs(depth+1);
			}
			
		}
	}
	
	public static boolean check(int row) {
		for(int i=0;i<row;i++) {
			if(map[i]==map[row]) return false;
			if(Math.abs(i-row)==Math.abs(map[i]-map[row])) return false;
		}
		
		return true;
	}
}

5. 결과

19일만에 다시푸는 데 꽤 막혔다.

6. 회고

이 문제는 조만간 다시 풀어봐야겠다. 그리고 이것과 비슷한 문제로 스도쿠 문제가 있던데 그것도 풀어볼 예정이다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212