(Java)백준 Queen 9663.N-Queen

1. 문제 조건

- 퀸은 가로, 세로, 대각 모든 방향으로 이동 가능

- N*N 체스판에 총 N개의 퀸을 놓아야 하는데 이 때 퀸들이 서로 공격이 불가해야 함.

2. 아이디어

- 2차원 배열[N][N]의 각 행을 돌며 퀸을 놓을 수 있는 지 체크(이전에 퀸을 놓은 위치마다 가로,세로,대각을 색칠하여 구분하기)

- 퀸을 놓을 수 있다면 퀸을 놓고 다음 행의 놓을 자리 찾으러 가기(재귀 활용)

- 퀸을 놓을 수 없다면 for문에서 continue;

 

3. 구현

- 처음에 퀸을 놓을 수 있는지 여부를 체크하기 위해 boolean을 활용해서 true(해당 자리에 퀸 오면 안됨)로 바꾸고 해당 재귀 함수가 끝나면 다시 false(해당 자리에 퀸 와도 됨)로 바꾸는 방식으로 접근했다. 그랬더니, 어떤 자리는 해당 함수가 종료됐을 때 false로 바뀌더라도 이전에 놓았던 퀸으로 인해 영향을 받아 그 자리를 고려하지 않아야 할 상황에서 해당 자리가 false로 바뀜으로서 자리 체크에 오류를 범하는 일이 발생했다.

 

- 위 문제를 해결하기 위해 배열의 타입을 boolean이 아닌 int로 바꾸고 1을 더했다가 빼는 방식을 사용했다. 그렇게 되면, 0일 때는 단 한번도 어떤 퀸에게도 공격받지 않는 자리이므로 퀸을 놓을 수 있다는 뜻이고, 0보다 커지는 순간 퀸에게 영향을 받을 수 있다는 뜻이므로 true와 false와 달리 전, 전전, 그 저어어어어언의 모든 퀸들의 영향력을 확인할 수 있다.

 

- 각 자리를 돌며 가로, 세로, 대각에 다른 퀸이 있는지 확인하는 방식이 아닌 퀸을 놓고 색칠하는 방식을 택했다 보니, 마지막 행까지 모든 퀸을 놓았는지 확인하고 cnt(퀸을 놓을 수 있는 방법의 수)를 더하는 if문의 위치에 있어서 시행착오를 겪었다. queen메서드의 재귀 함수 사용 시, 이미 check메서드를 한번 하고 들어오므로 마지막 행에 현재 보고 있는 열이 1이면 퀸을 놓을 자리가 있다는 것이고, 아니면 퀸을 둘 수 있는 곳이 없다는 의미이므로 if문을 check를 한 직후에 넣었어야 했다.

 

package Gold4;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main_9663n퀸 {


		static int[][] map;
		static int N;
		static int cnt;

		public static void main(String[] args) throws NumberFormatException, IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

				N = Integer.parseInt(br.readLine());
				map = new int[N][N];
				cnt = 0;
				queen(0, 0);
				System.out.println(cnt);

			}

		

		public static void queen(int r, int c) {
			if(N==1) {
				cnt =1;
				return;
			}
			if(r==N || c==N) {
				return;
			}
			// 마지막 열을 봤는데 queen을 놓을 수 없으면 해당 행 보는 함수 종료.

			
			
			if (c == N - 1 && map[r][c]!=1)
				return;
			for (int i = 0; i < N; i++) {
				if (map[r][i]!=0) continue;

				//가로세로 모든대각 체킹
				check(r, i, 1); // check
	            
			    // 마지막 행을 보는데 해당 자리에 놓을 수 있으면 cnt ++
				if (r == N - 1 && map[r][i]==1) {
					cnt++;}
				// 다음 행 놓을 자리 보러 가기.
				queen(r + 1, c);
				// 다음행 자리 보고 나왔으면 지나왔던 길 uncheck
				check(r, i, -1); // uncheck

			}
			

		}

		public static void check(int r, int c , int ch) {
			map[r][c] += ch;
			for (int i = 0; i < N; i++) {
				if(i!=c) map[r][i] += ch; // 가로 체크
				if(i!=r) map[i][c] += ch; // 세로 체크
			}
				for (int k = 1; k < N; k++) {
					if ((r + k) < N && (c + k) < N)
						map[r + k][c + k] += ch; // 대각 체크
					if ((r + k) < N && (c - k) >= 0)
						map[r + k][c - k] += ch;
					if ((r - k) >= 0 && (c - k) >= 0)
						map[r - k][c - k] += ch; // 대각 체크
					if ((r - k) >= 0 && (c + k) < N)
						map[r - k][c + k] += ch;
				
			}

		}
	

}