오늘도 푼 알고리즘 문제는 틀렸다.
언제쯤 이 오답 노트를 안쓰고 맞는 날이 올까
그래도 새로운 접근 방법을 배웠다.
접근
문제는 NXN 체스판에 N개의 여왕말을 둘 때 서로를 공격하지 않는 방법의 수를 모두 구하는 것이다.
따라서 처음에
- 2차원 상태 배열을 만들어서 여왕이 갈 수 있는 대각선, 가로선, 세로선을 모두 true로 표시하는 함수를 하나 만들자
- 여왕이 첫번째 줄을 탐색하여 서로를 공격하지 않는 경우
= 여왕이 두번째 줄을 탐색하여 서로를 공격하지 않는 경우
= 여왕이 N번째 줄을 탐색하여 서로를 공격하지 않는 경우
이므로 여왕이 첫번째 줄을 탐색하여 서로를 공격하지 않는 경우의 수만 고려해서 DFS의 백트래킹을 이용하자
이 계획이었으나 상태 배열을 통해 백트래킹 하는 것에는 문제가 있었다.
풀이는 "실패한 나의 풀이"에 설명되어져 있다.
기존에 존재하는 여왕이 만들어놓은 true를 백트래킹 하는 과정에서 다른 여왕의 true를 false로 만들어버린다는 문제가 발생한다.
따라서 이건 상태배열을 사용하여할 수 없다.
미리 놓여진 여왕말의 자료를 참조하되 상태 배열을 통해서가 아니라
미리 놓여진 여왕말들의 위치를 바탕으로 놓을 수 있는 위치인가에 대한 판단으로 조건문을 만들어야 한다.
과정
위치를 어떻게 저장할 것인가?
같은 행과 열에는 절대 존재할 수 없다는 것을 기억하면서
N개 값을 가지는 배열을 하나 만든다.
그 배열의 index는 행의 위치를 값은 열의 위치를 나타낸다.
이제 탐색을 시작한다.
앞서 설명한대로
여왕이 첫번째 줄을 탐색하여 서로를 공격하지 않는 경우
= 여왕이 두번째 줄을 탐색하여 서로를 공격하지 않는 경우
= 여왕이 N번째 줄을 탐색하여 서로를 공격하지 않는 경우
이므로 여왕이 첫번째 줄을 탐색하여 서로를 공격하지 않는 경우의 수만을 고려한다.
따라서 아래와 같이 탐색을 한다.
for(int i=0;i<N;i++){
arr[0]=i;
queen(0,i,0);
}0번째 행에 놓고 그 다음 1번째, 2번째,...N번째 행에 놓이기 때문에
재귀함수를 통해서 queen(여왕이 놓여진 행+1,열 탐색)을 불러오도록 한다.
static void qeen(int x, int y,int cnt){
if(cnt==N-1){
answer++;
return ;
}else{
for(int i=0;i<N;i++){
if(make_road(x+1,i)){
arr[x+1]=i;
queen(x+1,i,x+1);
}
}
}
}그 곳에 말이 놓일 수 있는 지의 여부를 미리 놓여진 여왕말의 위치를 통해서 판단할 수 있다.
그 함수는 아래와 같다.
static boolean make_road(int x, int y){
for(int i=0;i<x;i++){
//같은 열에 존재하는 경우 (행은 당연히 다름)
if(arr[i]==y) return false;
//대각선에 존재하는 경우
if(Math.abs(y-arr[i])==Math.abs(i-x)){
return false;
}
}
return true;
}이를 바탕으로 풀이하였다.
실패한 나의 풀이
import java.util.*;
import java.io.*;
public class Main{
static boolean[][] visit;
static int N;
static int answer=0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
visit = new boolean[N][N];
for(int i=0;i<N;i++){
make_road(0,i);
queen(0,i,0);
make_road_false(0,i);
}
bw.write(Integer.toString(answer));
bw.flush();
bw.close();
br.close();
}
static void queen(int x, int y,int cnt){
if(cnt==N-1){
answer++;
return ;
}else{
for(int i=0;i<N;i++){
if(visit[x+1][i]==false){
make_road(x+1,i);
queen(x+1,i,x+1);
make_road_false(x+1,i);
}
}
}
}
static void make_road(int x, int y){
visit[x][y]=true;
for(int i=0;i<N;i++){
visit[i][y] =true;
visit[x][i] =true;
if( x-i>=0 && y-i >=0 )
visit[x-i][y-i]=true;
if( x+i<N && y+i<N)
visit[x+i][y+i]=true;
if( x-i>=0 && y+i <N )
visit[x-i][y+i]=true;
if( x+i<N && y-i>=0)
visit[x+i][y-i]=true;
}
}
static void make_road_false(int x, int y){
visit[x][y]=false;
for(int i=0;i<N;i++){
visit[i][y] =false;
visit[x][i] =false;
if( x-i>=0 && y-i >=0 )
visit[x-i][y-i]=false;
if( x+i<N && y+i<N)
visit[x+i][y+i]=false;
if( x-i>=0 && y+i <N )
visit[x-i][y+i]=false;
if( x+i<N && y-i>=0)
visit[x+i][y-i]=false;
}
}
}이 방법의 문제는 백트래킹을 할 때 발생한다.
위 상황이었다고 가정하고
백트래킹을 3행,2열(4번째 줄의 3번째 칸)의 Queen에서 한다고 하자
문제점이 보인다.
바로 2행에 존재하는 Queen이 True로 설정해놓았던 것까지 False로 만들어버리는 것이다.(0행, 1행의 Queen이 만든 True까지 False로 만들어버린다.)
따라서 저 방법은 잘못된 것이다!
상태배열을 통한 백트래킹은 미리 놓여진 여왕말의 true값을 false로 바꿔버린다. 따라서
미리 놓여진 여왕말의 위치 정보를 바탕으로 놓일 수 있는 여왕말의 위치를 찾는 과정이 필요하다.
성공한 풀이(자바)
import java.util.*;
import java.io.*;
public class Main{
static int[] arr;
static int N;
static int answer=0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
arr = new int[N];
for(int i=0;i<N;i++){
arr[0]=i;
queen(0,i,0);
}
bw.write(Integer.toString(answer));
bw.flush();
bw.close();
br.close();
}
static void queen(int x, int y,int cnt){
if(cnt==N-1){
answer++;
return ;
}else{
for(int i=0;i<N;i++){
if(make_road(x+1,i)){
arr[x+1]=i;
queen(x+1,i,x+1);
}
}
}
}
static boolean make_road(int x, int y){
for(int i=0;i<x;i++){
//같은 열에 존재하는 경우 (행은 당연히 다름)
if(arr[i]==y) return false;
//대각선에 존재하는 경우
if(Math.abs(y-arr[i])==Math.abs(i-x)){
return false;
}
}
return true;
}
}