[level 2] N-Queen - 12952

문제 링크

성능 요약

메모리: 380 MB, 시간: 1668.37 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 09월 16일 11:47:20

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

---

입출력 예

n	result
4	2

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

---

풀이

• DFS로 퀸을 놓을 수 있는지 확인하여 경우의 수 구하기

---

코드

class Solution {
    
    public static int N, cnt;
	public static boolean[][] board;

	public int solution(int n) {

		N = n;
		cnt = 0;
		board = new boolean[N][N];
		dfs(0);

		return cnt;
	}

	public static void dfs(int row) {

		// 마지막 줄까지 N개의 퀸을 놓았으면
		if (row == N) {
			cnt++;
			return;
		}

		// 각 열마다 퀸을 놓을 수 있는지
		for (int col = 0; col < N; col++) {

			// 퀸을 놓을 수 있으면
			if (canPut(row, col)) {
				board[row][col] = true;
				dfs(row + 1);
				board[row][col] = false;
			}
		}

	}

	public static boolean canPut(int r, int c) {

		// 우상, 우, 우하, 하, 좌하, 좌, 좌상, 상 (8방향 탐색)
		int[] dx = { 1, 1, 1, 0, -1, -1, -1, 0 };
		int[] dy = { -1, 0, 1, 1, 1, 0, -1, -1 };

		for (int i = 0; i < 8; i++) {
			int rx = c;
			int ry = r;

			// 해당 방향으로 이동
			for (int j = 0; j < N; j++) {
				rx += dx[i];
				ry += dy[i];

				// 보드 밖으로 나가면 continue
				if (rx < 0 || rx >= N || ry < 0 || ry >= N)
					continue;

				// 해당 칸에 퀸이 이미 존재하면 false 반환
				if (board[ry][rx])
					return false;
			}

		}

		// 문제없으면 true 반환
		return true;
	}
}