SWEA : 2806 N-Queen(JAVA)

문제

문제
시간 제한 4초, 힙+정적 256MB 이내 혹은 스택 256MB 이내

퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다.
N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇가지가 있을까?
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력
테스트 케이스의 수 T
보드의 가로와 세로 값, 퀸의 개수 (1 ≤ N ≤ 10)

출력
퀸을 놓는 방법의 수

풀이

문제를 읽은 후의 생각들을 쭉 나열해보면...
일단 N도 10 이내고 시간 제한도 4초라, 완전탐색으로 풀어볼 만하다는 생각을 했다.
재귀를 사용하여 풀되, 위에서 내려오며 퀸을 놓는다.
퀸을 놓을 수 있는지 확인할 때 위 세로, 위 대각선을 파악하고 해당 위치 중에 퀸이 있는 경우 더 재귀문을 돌리지 않는다.

간단하게 2로 예시를 들어 생각해보면...
0,0에 넣는 경우 row++하고 1,0과 1,1에 넣는 경우를 check 함수로 확인한다.
0,1에 넣는 경우 row++하고 1,0과 1,1에 넣는 경우를 check 함수로 확인한다.
둘 다 더 내려갈 row가 없음 -> 0 반환, 모든 경우의 수가 0을 반환 => 값은 0

4로 예시를 들면...
0,0에 넣는 경우 row++ 하고
1,0에 넣는다 → 안 됨(진행X)
1,1에 넣는다 → 안 됨(진행X)
1,2에 넣는다 → 가능하므로 진행, 2,0 2,1 2,2 2,3에 넣어보며 되는지 진행
1,3에 넣는다 → 가능하므로 진행, 2,0 2,1 2,2 2,3에 넣어보며 되는지 진행

이 생각을 기반으로 작성해본 첫 코드는 이러했다. (🚧 잘못된 코드 🚧)

public class Solution {
	static int N;
	static int[][] drc = {
			{-1, 0},
			{-1, -1}, {-1, 1}
	};
	
	static int dfs(boolean[][] board, int row, int col) {
		int result = 0;
		
		if(!check(board, row, col)) { // 불가능한 경우 추가 탐색 X
			return 0;
		}
		
		if(row == N-1) { // check는 이미 상단에서 통과, row == N이면 끝, return 1;
			return 1;
		}
		
		for(int i=row; i<N-1; i++) {
			for(int j=col; j<N; j++) {
				board[i][j] = true;
				for(int k=0; k<N; k++) {
					result += dfs(board, i+1, k);
				}
				board[i][j] = false;
			}
		}
		
		return result;
	}
	
	static boolean check(boolean[][] board, int row, int col) {
		for(int i=0; i<3; i++) { // drc를 순회하면서 더하고 빼고 할 거임
			int nR = row + drc[i][0];
			int nC = col + drc[i][1];
			
			// r, c에 drc 3개를 각각 더하며 0이나 N을 넘지 않을 때까지 확인
			while(nR >= 0 && nR < N
					&& nC >= 0 && nC < N) {
				
				if(board[nR][nC]) {
					return false;
				}
				
				nR += drc[i][0];
				nC += drc[i][1];
			}
		}
		return true;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		// N*N 보드에 N개의 퀸을 공격하지 못 하게 놓는 경우
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			// 확인할 때 : 위만 본다 (아래는 고려 X)
			// 위에서부터 내려오면서 놓을 거니까
			N = Integer.parseInt(br.readLine());
			
			boolean[][] board = new boolean[N][N];
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					board[i][j] = false;
				}
			}
			
			int result = 0;
			// check하고 true받는 경우에만 다음 col로 넘긴다
			bw.write("#" + tc + " " + dfs(board, 0, 0) + "\n");	
		}
		bw.flush();
		bw.close();
		br.close();
	}
}

1과 2까지는 잘 작동했지만 4의 값이 40이 나왔다.
콘솔창에 값을 찍어보니까 매 열에 최소 1개는 있어야 N개가 되는데, 어디선가 false로 변한 배열도 들어와서 같이 check를 돌고 같이 출력되는 모양이었다.

수정을 계속 하던 와중... row를 굳이 for문으로 돌 필요가 없다는 걸 깨달았다.
내 생각에는 0~N까지 row를 돌아야 한다고 생각해서 저렇게 작성했었는데, 각 행에는 퀸을 하나만 두면 되므로 row까지 for문을 돌릴 필요 없이 col만 for문을 돌리면 됐다.

row는 재귀함수의 매개변수로 보내서 1씩 늘릴 것이니 for문을 제거한다.
col을 0~N까지 순회하며 놓기 전, check 함수로 놓을 수 있는 위치인지 확인한다. 퀸을 놓을 수 있는 경우, board[row][col] = true;로 변경해 퀸을 놓았다고 배열의 값을 변경해주고, 재귀문을 돌린다.
이후 다음 col 값을 돌기 전 false;로 배열의 값을 변경해준다.

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

public class Solution {
	static int N;
	static int[][] drc = {
			{-1, 0},
			{-1, -1}, {-1, 1}
	};
	
	static int dfs(boolean[][] board, int row) {
		int result = 0;
		
		if(row == N) { // check는 이미 상단에서 통과, row == N이면 끝, return 1;
			return 1;
		}
		
		for(int col=0; col<N; col++) {
			if(check(board, row, col)) {
				board[row][col] = true;
				result += dfs(board, row+1);
				board[row][col] = false;
			}
		}
		
		return result;
	}
	
	static boolean check(boolean[][] board, int row, int col) {
		for(int i=0; i<3; i++) { // drc를 순회하면서 더하고 빼고 할 거임
			int nR = row + drc[i][0];
			int nC = col + drc[i][1];
			
			// r, c에 drc 3개를 각각 더 하며 0이나 N을 넘지 않을 때까지 확인
			while(nR >= 0 && nR < N
					&& nC >= 0 && nC < N) {
				
				if(board[nR][nC]) {
					return false;
				}
				
				nR += drc[i][0];
				nC += drc[i][1];
			}
		}
		return true;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		// N*N 보드에 N개의 퀸을 공격하지 못 하게 놓는 경우
		
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			N = Integer.parseInt(br.readLine());
			
			boolean[][] board = new boolean[N][N];
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					board[i][j] = false;
				}
			}
			
			bw.write("#" + tc + " " + dfs(board, 0) + "\n");	
		}

		bw.flush();
		bw.close();
		br.close();

	}

}

문제를 풀며

한 번 생각을 잘못해서 삽질하기 시작하면 정말 시간을 끝도 없이 잡아먹는 것 같다. 이럴 땐 그냥 다른 문제 풀다가 돌아와서 코드 전부 주석 처리하고 처음부터 다시 생각해봐야 하나 고민이 된다. 지금이야 연습 삼아 푸는 거니 잠깐 걸으며 머릿속을 정리하는 시간을 가질 수 있지만, 코딩 테스트를 볼 때는 그럴 수 없으니까... 🥺

흠... 처음부터 코드를 꼬이지 않게 짤 수 있게끔 최대한 연습을 많이 해보는 수 밖에 없겠다!