[프로그래머스] N-Queen Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

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

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

 

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

2. 입력

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

3. 예제

n	result
4	2

4. 풀이

퀸은 위 그림처럼 상하 좌우 1시, 5시, 7시, 11시 방향 대각선으로 모두 움직일 수 있습니다.

 

퀸은 좌우로 이동이 가능하므로 입력으로 주어진 N의 칸에서 N개의 퀸이 있으려면 각 행에 1개의 퀸만 존재할 수 있습니다.

 

그러므로 체스판에서 각 행의 열을 순회하면서 퀸이 올 수 있다면 다음 행에서 올 수 있는 위치를 찾는 것을 반복하여 N개의 퀸이 있을 수 있는지 없는지 판단할 수 있습니다.

 

N이 4인 채 스판을 예로 들겠습니다.

 

빈 채 스판에서 파란색의 위치에 첫 퀸은 위치할 수 있습니다. 그러므로 해당 위치에 퀸을 놓고 다음 행에서 올 수 있는 퀸의 위치를 찾습니다.

 

1번째 행에 놓인 퀸에 의해서 해당 위치의 퀸은 놓을 수 없으므로 다음 열로 이동하여 확인을 진행합니다.

 

1번째 행에 놓인 퀸에 의해서 해당 위치의 퀸은 놓을 수 없으므로 다음 열로 이동하여 확인을 진행합니다.

 

1번째 행에 놓인 위치의 퀸과 관련이 없는 위치이므로 해당 위치에 2번째 퀸을 놓고 다음 행으로 이동합니다.

 

1번째 행에 놓인 퀸에 의해서 해당 위치의 퀸은 놓을 수 없으므로 다음 열로 이동하여 확인을 진행합니다.

---

2번째 행에 놓인 퀸에 의해서 해당 위치의 퀸은 놓을 수 없으므로 다음 열로 이동하여 확인을 진행합니다.

 

3번째 행의 경우 모든 열을 순회하였지만 퀸을 놓을 수 있는 위치가 존재하지 않기 때문에 이전인 2번째 행으로 돌아가서 열의 위치를 변경합니다.

이때 또한 1번째 행에 놓인 퀸과 관련이 없는지 확인을 진행하고 놓을 수 있으면 해당 위치에 퀸을 놓습니다.

---

이번 또한 3번째 행의 순회에서 가능한 퀸의 위치는 존재하지 않습니다. 또한 2번째 행에서 이동할 열 또한 존재하지 않으므로 1번째 행의 퀸의 위치를 변경합니다.

그리고 다시 2번째 행의 1번째 열부터 순회를 하면 가능한지 확인을 합니다.

---

 

이러한 과정을 반복하여 최종 체스판에 퀸이 N개가 놓이게 되면 정답 개수를 1개 증가하여 N개의 퀸이 몇 종류 나올 수 있는지 카운팅 하여 문제를 풀 수 있습니다.

 

5. 코드

전체 코드는 Git에 있습니다.

private int answer = 0;

public int solution(int n) {
	int[] map = new int[n];
	Backtrack(n, 0, map);
	return answer;
}

public void Backtrack(int n, int rowIndex, int[] map) {
	if (n == rowIndex) {
		answer++;
	} else {
		for (int i = 0; i < n; i++) {
			map[rowIndex] = i;
			if (check(map, rowIndex)) Backtrack(n, rowIndex + 1, map);
		}
	}
}

public boolean check(int[] map, int rowIndex) {
	for (int i = 0; i < rowIndex; i++) {
		if (map[i] == map[rowIndex]) return false;
		if (Math.abs(map[i] - map[rowIndex]) == Math.abs(i - rowIndex)) return false;
	}

	return true;
}