👀 문제
https://www.acmicpc.net/problem/9663
👊 도전
풀이 방법 1
1. 설계
- 체스판 위에 퀸의 위치를 저장할 이차원배열 visit를 생성한다.
- DFS를 이용하여 모든 경우의 수를 찾되, 퀸의 조건에 맞게 앞 뒤 좌우 대각선에 퀸이 존재할 경우 탐색을 종료한다.
- 퀸을 놓을 수 있는 방법의 수를 리턴한다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.Scanner;
/**
*
* @author HEESOO
*
*/
public class Main {
static int n;
static int answer;
static boolean visit[][];
public static void dfs(int x){
if(x==n){
answer++;
return;
}
for(int i=0;i<n;i++){
if(!check(x, i)) continue;
visit[x][i]=true;
dfs(x+1);
visit[x][i]=false;
}
}
public static boolean check(int x, int y){
for(int i=0;i<n;i++){
if(i<=y&&visit[x][i]) return false;//행
if(i<=x&&visit[i][y]) return false;//열
//오른쪽 아래로 가는 대각선
if(x+i<n&&y+i<n&&visit[x+i][y+i]) return false;
//왼쪽 위로 가는 대각선
if(x-i>=0&&y-i>=0&&visit[x-i][y-i]) return false;
//왼쪽 아래로 가는 대각선
if(x-i>=0&&y+i<n&&visit[x-i][y+i]) return false;
//오른쪽 위로 가는 대각선
if(x+i<n&&y-i>=0&&visit[x+i][y-i]) return false;
}
return true;
}
public static void main(String[] args){
Scanner input=new Scanner(System.in);
n=input.nextInt();
visit=new boolean[n][n];
answer=0;
dfs(0);
System.out.println(answer);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- DFS를 이용한다.
- 퀸을 놓을 수 있는 곳은 true로 바꾸고 퀸을 놓는다.
- 퀸을 놓기 전에, check()를 통해 놓을 수 있는 곳인지 체크한다.
- 한 행, 열에는 하나의 퀸만 놓을 수 있다.
- 말을 놓은 후에는 다음 행에서 놓을 수 있는 위치를 찾기 위해 재귀를 호출한다. 이때 파라미터는 다음 행인 x+1이다.
- check()에서 해당 위치에 퀸을 놓을 수 있는지 확인한다.
- 파라미터로 받은 (x,y)를 기준으로 같은 행, 열, 대각선에 true로 표시되어 퀸이 존재하는 곳이 있다면 false를 리턴하여 (x,y)에는 퀸을 놓을 수 없다고 알려준다.
👏 해결 완료!
참고
- 백준 9663번 N-Queen :: 마이구미 https://mygumi.tistory.com/199
- [백준] 9663번 N-Queen https://whereisusb.tistory.com/142