SWEA_D3_2806

📁 [D3_2806] N-Queen

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


public class Solution{
	// 결과 - 경우의 수
	static int res;

	// 배열
	static int[] arr;

	static int N;

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

		int TC = Integer.parseInt(br.readLine());

		for (int T = 1; T <= TC; T++) {
			sb.append("#").append(T).append(" ");

			// 보드의 크기
			N = Integer.parseInt(br.readLine());

			// 열의 위치값 저장 배열
			arr = new int[N];
			
			res = 0;
			go(0);

			sb.append(res).append("\n");
		}
		System.out.println(sb);
	}

	// 재귀 - 순열
	static void go(int row) {
		// 기저조건
		if (row == N) {
			// 조건에 충족한 값이 끝까지 들어왔으므로
			res++;
			return;
		}

		for (int i = 0; i < N; i++) { // 행 돌면서 열의 위치값 저장, 재귀 호출
			arr[row] = i; // 행 돌면서 열의 위치값 저장

			// 조건 충족하면 다음 재귀 호출
			// 가지치기 조건
			if (check(row)) {
				go(row + 1);
			}
		}

	}
	
	// 조건 메서드
	static boolean check(int row) {
		for(int i=0; i<row; i++) {
			// 같은 열에 위치
			if(arr[row] == arr[i]) {
				return false;
			}
			
			// 대각선에 위치
			if(row-i == Math.abs(arr[row] - arr[i])) {
				return false;
			}
			
			// 같은 행에 위치
			if(row == i) {
				return false;
			}
		}
		return true;
	}
}

🤔 나의 생각

백트래킹을 연습해 볼 수 있는 문제였다.
특이점은 행과열을 이차원 배열로 받지 않고 하나의 일차배열에 열의 위치값을 넣었다.
한마디로 for문의 변수는 행이 되고 배열 값은 열이 되는 원리이다.
이해가 되면 쉽다 생각하겠지만 잘 안되었을땐 그냥 이차원배열을 써도 괜찮을 것 같다.
물론 공간복잡도와 시간복잡도에서는 차이가 있겠지만.. N이 그렇게 크지 않다면 크게 차이는 나지 않을 것이라고 생각한다.
점점 문제를 풀면 풀수록 시간 복잡도와 공간 복잡도의 중요성에 대해 느끼게 된다 !!