[Java]백준 BaekJoon.AC 9663 : N-Queen(브루트포스, 백트래킹)

 

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

9663번: N-Queen

 

 

와... 힘든 문제였다.

사실 이 문제는 이전에 해결한 문제였다.(그때도 힘들게 다른 코드 참고하며 풀었던 걸로 기억함)

그래도 풀어봤던 문제니 복습겸 가볍게 풀자~ 싶었는데 이 녀석이 며칠을 고생시킬 줄 몰랐다.

약간 참고해가며 그래도 구동은 시켰는데, 문제는 시간 초과..

 

이 문제를 풀며 다시 한 번 깨달은 점은, 난 정말 필요하지 않은 부분까지 신경쓰고 집착한다는 것이다.

<<아래 코드는 틀린 코드이다>>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	static int N;
	static int result = 0;
	static int[][] put;
	static boolean[][] visit;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
		N = Integer.parseInt(br.readLine());
		put = new int[N][N];
		visit = new boolean[N][N];
		
		isPossible(0);
		
		System.out.print(result);
	}
	
	
	public static void imPossible(int col, int row) {
		//상하좌우
		for(int i=0; i<N; i++) {
			put[col][i] = -1;
			put[i][row] = -1;
		}

		int a = col;
		int b = row;
		
		if(a<=b) {
			int mis = b - a;
			for(int i=0; i<N-mis; i++) {
				put[i][i+mis] = -1;
			}
		}else {
			int mis = a - b;
			for(int i=0; i<N-mis; i++) {
				put[i+mis][i] = -1;
			}
		}
		
		if(a+b<N) {
			int mis = a + b;
			for(int i=0; i<=mis; i++) {
				put[mis-i][i] = -1;
			}
		}else {
			int mis = a + b;
			for(int i=N-1; i>mis-N; i--) {
				put[i][mis-i] = -1;
			}
		}
		
		put[col][row] = 1;
		
	}
	
	
	public static void isPossible(int num) {
		
		if(num==N) {
			result++;
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(put[num][i] == 0) {
					
				put[num][i] = 1;
				visit[num][i] = true;
					
				imPossible(num, i);
				isPossible(num+1);
					
				visit[num][i] = false; //이전상태로 돌아가기
				for(int k=0; k<N; k++) {
					for(int l=0; l<N; l++) {
						put[k][l] = 0;
					}
				}
						
				
				for(int k=0; k<N; k++) {
					for(int l=0; l<N; l++) {
						if(visit[k][l]==true) {
							imPossible(k, l);
						}
					}
				}
				
			}
		}
		
	}
}

 

isPossible 메소드를 구현하며 다른 코드를 참고한 적이 있다.

(isPossible 메소드 중 가장 먼저 작성된 for문 얘기하는 중)

난 2차원 배열이니 당연히 이중 for문을 이용했다.

그런데 다른 사람들은 단문을 사용하는게 아니던가.

처음엔 왜 그런지 몰랐다. 나랑 코드가 달라서 그냥 방식이 다른 줄 알았다.

 

 

시간초과로 코드를 줄일 때 비로소 깨달았다. 이 문제의 큰 핵심을...

퀸을 놓을 때 가로 세로 대각선이 모두 겹치지 않아야 한다. 이 말을 너무 쉽게 생각했다.

 

난 (0,0)부터 시작했으니 첫째줄부터 시작했다고 말할 수 있다.

만약 (0,0)에 퀸을 뒀다고 가정하면, 이 줄엔 무조건 퀸을 더 놓을 수 없으니 퀸 하나를 놓으면 그 줄은 더이상 볼 필요조차 없게 된다....!

이 점을 간과하고 난 모든 배열의 문을 두드렸다. 혹시 우리 퀸 들어갈 자리 있냐고...

퀸을 두면 바로 그 다음줄로 넘어가도 된다는 것, 그리고 한 줄엔 무조건 퀸이 하나씩은 있어야 조건을 만족한다는 것.

 

 

 

큰 깨달음을 얻고 코드를 수정했다.

그런데, 여전히 시간초과가 발생했다.

다른 사람의 코드를 또 참고했다.

 

 

다른 건 다 비슷한데 퀸 금지구역...?(imPossible메소드)을 감별하는 코드가 또 다르더이다.

성능에 별 차이가 없을 것 같았는데, 이거 말곤 다른게 없었다.

심지어 반절만 적어둔 듯한 코드라 나 주제에 그 코드가 이상하다 여겼다ㅋㅋㅋㅋ;;

또 찬찬히 뜯어봤다.

 

아니 그랬더니, 고수님의 코드는 윗대각선의 불가능 여부는 아예 고려하지 않은거 있지 않은가...!!

해당 배열을 기준으로, 좌우와 위도 고려할 필요가 없다.

뒤통수를 심지어 같은 곳에 한 대 더 맞았다.

옆과 위는 아예 고려할 필요가 없구나... 이런식으로 시간을 단축하는구나. 큰 가르침을 얻었다.

 

 

난 문제가 요구하는 모든 걸 구하려는 습관이 있다. 빠르게 문제를 푸는 데엔 정말 안좋은 습관이다,,,

늘 시험시간에 허덕이는 나는 너무 잘 아는 내 악습이다...(이 자체가 나쁘다고 생각하진 않으나, 시험에서 좋을 건 없다고 생각한다.)

항상 구하라고 하지도 않은 것까지 친절하게 다 구해준다ㅋㅋㅋ; 하..

 

 

이마를 탕탕 치며 코드를 수정했...

Aㅏ.. 또 시간초과가 나오네...(글 쓰면서 코딩중)

 

도대체 무슨 문제냐 싶었는데, 설마설마 하며 int배열을 boolean으로 그냥 갈아버리니 통과가 된다~~^^

너무 힘들어서.... 그냥 앞뒤 안보고 냅다 대충 고쳤고, 위에서 정성껏 설명한 코드 덕택에도 통과했는지의 여부는 모르겠다^^

그냥 int배열을 그,, 수정 많이하는 배열...? 로 사용하지 말아야 하는 것이어따...

후... 아주 큰 가르침을 얻었다....... 역시 가르침은 고통을 통해 얻어지는 것....ㅠㅠ

 

그리 좋은 코드는 아닌 것 같다.. 나중에 다시 한 번 손봐야겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	static int N;
	static int result = 0;
	static boolean[][] put;
	static boolean[][] visit;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
		N = Integer.parseInt(br.readLine());
		put = new boolean[N][N];
		visit = new boolean[N][N];
		
		isPossible(0);
		
		System.out.print(result);
	}
	
	
	public static void imPossible(int col, int row) {
		//밑
		for(int i=col; i<N; i++) {
			put[i][row] = true;
		}

		int a = col;
		int b = row;
		
		while(0<=b && b<N && 0<=a && a<N) {//왼밑
			put[a++][b--] = true;
		}
		
		int c = col;
		int d = row;
		
		while(0<=c && c<N && 0<=d && d<N) {//오른밑
			put[c++][d++] = true;
		}
		
	}
	
	
	public static void isPossible(int num) {
		
		if(num==N) {
			result++;
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(put[num][i] == false) {
					
				put[num][i] = true;
				visit[num][i] = true;
					
				imPossible(num, i);
				isPossible(num+1);
					
				visit[num][i] = false; //이전상태로 돌아가기
				for(int k=0; k<N; k++) {
					for(int l=0; l<N; l++) {
						put[k][l] = false;
					}
				}
						
				
				for(int k=0; k<N; k++) {
					for(int l=0; l<N; l++) {
						if(visit[k][l]==true) {
							imPossible(k, l);
						}
					}
				}
				
			}
		}
		
	}
}