(JAVA) 백준 9663번 : N-Queen

 

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

 

후..

 

백트래킹 문제인데

백트래킹의 개념을 잘 숙지하지 못해서

시간 한참 걸렸다..

 

 

 

백트래킹은 한마디로 정의하자면

 

하나씩 짚어가다가 조건에 일치하면 거기서 종료.

 

다시 돌아와서 짚어가던거 마저 짚어가는 것

 

이다.

 

 

 

 

주어진 문제의 조건은

 

체스의 퀸의 성격을 이해해야 한다.

 

퀸은 상하좌우 + 좌우대각선을 이동할 수 있다.

 

 

그렇기 때문에

하나의 퀸을 놓게 되면

 

그 퀸의 상하좌우 + 좌우대각선에는 퀸을 놓을 수 없다는 뜻이다.

 

이것을 백트래킹으로 표현하면 된다.

 

 

N-Queen에서의 백트래킹 풀이 접근 방법(출처 : https://mygumi.tistory.com/199)

위 블로그에 게시되어있던 그림이

이 문제를 하나의 그림으로 표현할 만큼

간단 명료하게 나타내서 잠깐 참고했다.

 

위 그림이

백트래킹이다.

 

 

참고할 사항은

 

1) 한 줄에서는 하나의 퀸만 놓을 수 있다.(상하좌우 이동 가능하기 때문)

 

2) 그렇기 때문에 Y좌표는 줄 단위로 건너뛰고, X좌표는 0부터 끝까지 탐색할 수 있다.

 

3) 저는 퀸 놓는 Boolean 배열을 2차원으로 설정했지만, 이를 1차원으로 설정하고 해결하면 더욱 속도가 향상된다. (저는 못했음) 

 

 

 

 

매커니즘

---

1. 첫 번째 줄부터 백트래킹을 시작한다.

 

 

2. 해당 자리에 퀸을 놓을 수 있다면(해당 x, y좌표를 바탕으로 퀸이 놓여져 있는지 탐색)

 

** 퀸 탐색 시 밑으로는 움직이지 않고, 왼쪽 대각선 - 위 - 오른쪽 대각선 만 움직여도 된다.

그 이유는 첫 번째 줄 부터 시작해서 한 줄씩 내려가기 때문이다.

 

 

3. 현재 위치를 True로 설정(퀸을 놓았다!) 한 다음 다음 줄로 이동해서 x좌표 0~n까지 탐색 시작

 

 

4. 현재 위치를 False로 설정(퀸을 놓을 수는 있지만, 여기 안놓을래) 한다.

 

** 이렇게 False로 해놓으면 다음 x좌표를 진행할 때는 이전 x,y좌표에는 퀸을 놓지 않았다고 판단할 수 있기 때문이다.

 

 

 

 

감사합니다.

 

 

소스코드

---