[백준]13-백트래킹/5-N-Queen/9663 풀이 JAVA

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

 

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

 

풀이 1 (JAVA)

내가 이해하기 어려웠기 때문에... 추가 설명도 덧붙인다.

일단 퀸은 가로, 세로, 대각선으로 이동할 수 있다.

그래서 퀸끼리 서로 공격할 수 없게 하려면

	●
			●
●
		●

이런 식으로 한 행에 하나의 퀸(●)이 들어가야 한다. (n=4)

 

n*n 체스판에는 총 n개의 행이 있어서 column 배열은 new int[n]으로 생성한다.

위 그림을 배열로 나타내면 {1, 3, 0, 2}가 된다.

 

이제 중요한 것은 index 위치에 퀸을 두어도 되는지 체크하는 방법이다.

 

1, 하나의 행에 하나의 퀸만 들어갔는지 체크하는 방법

-가로

column 배열 자체가 n개의 헹을 나타내기 때문에 딱히 필요 없다.

 

-세로

• column[index] == column[i]

위 코드에서 index(현재 퀸을 둔 위치)와 i의 column 값이 같다는 것을 그림으로 보면 이런 식이다.

	●
			●
●
	●

위 그림은 column = {1, 3, 0, 1}을 나타내고,

column[0] == column[3]의 값이 1로 같다.

즉, 하나의 행(가로)에 하나의 퀸이 있지만, 세로(열)에 퀸이 있어서 공격할 수 있게 된다.

 

2, 대각선 방향에 퀸을 둘 수 있는지 체크하는 방법

• Math.abs(index - i) == Math.abs(column[index] - column[i])

		●
			●
●
		●

위 그림은 column = {2, 3, 0, 2}를 나타낸다.

●부분인 column[0]과 column[2]는 대각선으로 마주보고 있다.

이를 체크하는 방법은 밑변과 높이가 같은지 확인하는 것이다.

아래 그림을 다시 표현하면 아래와 같다.

index	column[index]
0			2
1				3
2	0
3			2

-밑변

• index - i

2 - 0 = 2

 

-높이

• column[index] - column[i])

2 - 0 = 2

 

●부분도 잘 체크할 수 있도록 절댓값을 씌워준다.

 

풀이 2 (JAVA)

이 풀이는 퀸을 둔 위치와 그 대각선 자리에 다른 퀸을 두지 못하게 상태를 바꿔놓는 방법을 쓰고 있다.

col[i], dig1[index + i] , dig2[n - index - i]가 모두 false이면 퀸을 놓을 수 있다는 뜻이다.

그래서 그 자리에 퀸을 놓고(col[i] = true)

퀸이 놓인 자리의 대각선(↗, ↘)을 true로 바꾸어(dig1[index + i] =  dig2[n - index - i] = true)

다른 퀸을 놓을 수 없게 하는 것이다.

 

대각선은 왜 dig1[index + i], dig2[n - 1 - index - i] 이런 방법으로 구하는지는 다음과 같다.

1,  대각선(↗) 자리를 false로 바꾸기

dig1(↗)은 행 + 열의 값으로 알 수 있다.

행 + 열	0	1	2	3
0	0	1	2	3
1	1	2	3	4
2	2	3	4	5
3	3	4	5	6

0, 1, 2, 3, 4, 5, 6 숫자들이 곧 대각선(↗)이자 dig1의 인덱스가 된다.

만약 행 + 열(index + i)의 값이 3이었다면

dig1[3] = false가 되는데, 이는 위 그림의 3의 자리에 놓을 수 없게 되었단 의미가 된다. 

 

2, 대각선(↘) 자리를 false로 바꾸기

dig2(↘)의 값은 n + 행 - 열로 알 수 있다. 여기서 n은 4이다.

n + 행 - 열	0	1	2	3
0	4	3	2	1
1	5	4	3	2
2	6	5	4	3
3	7	6	5	4

1, 2, 3, 4, 5, 6, 7 숫자들이 곧 대각선(↘)이자 dig2의 인덱스가 된다.

위와 같이 dig2의 인덱스가 곧 그 숫자가 써있는 대각선을 의미한다.

 

n = 4일 때, 대각선을 false로 바꿀 때 최대 숫자는 7이기 때문에

n * 2인 8로 넉넉히 dig 배열을 선언해준다.

 

---

이해하는데 하루가 꼬박 걸렸다^^