[Java] 백트래킹 (N-Queen)

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

9663번: N-Queen

 

 

학교 전공 시간에 너무 듣기 싫어서 오랜만에 문제를 풀어봤다.

물론 전공시간 동안 못 풀어서 집에서 마저 풀었다.

 

체스에 조예가 깊었던 나는 맘에 드는 제목을 보고 덥석 풀어봤지만 시간복잡도의 늪에 빠져 몇 시간을 헤맸다.

3트 끝에 겨우 통과했다.

 

그럼 내가 처음에 제시했던 아이디어와 그 이후 가지치기로 시간복잡도를 줄인 코드를 살펴보자. 

 

3가지 방법이 생각났다.

1. Pair(x, y) 클래스를 생성 후 Set을 만들어서 중복을 허락하지 않는 조합 뽑기

2. 브루트포스

3. visited[x][y] 배열을 만들고 dfs 백트래킹으로 풀기

 

1번을 시도 해봤는데 Pair는 클래스라서 원시타입과 다르게 이런저런 제약이 많아서 포기했다.

 

2번은 아무리봐도 최소 3중 for문이고 4중 for문이면 풀 거 같았는데 이건 말도 안 되기 때문에 바로 포기했다.

 

그럼 3번으로 풀어보자!

 

3번으로 정하고 처음 나온 코드

 

 

 

1. (0,0) 부터 x축으로 1씩 커지면서 dfs를 돌림

2. 만약 안전한 위치라면 퀸을 놓고 depth를 +1 올리고 다시 dfs를 돌리는 전형적인 백트래킹 방식

3. 안전한 지역은 현재 내가 놓을 퀸의 위치와 이전에 놓인 퀸의 위치를 계산해서 판단 (2중 for문 사용)

4. 만약 안전한 위치가 아니라면 depth를 그대로 둔 채 다시 이동

 

 

 

2번째 코드

 

 

📌 Idea 1. 생각해보니까 한 행에 퀸을 놓으면 해당 행에서는 다시 퀸을 놓을 수 없다 

퀸이 놓여지면 그 뒤는 스킵하고 바로 아래 열로 이동하자

 

📌 Idea 2. 안 그래도 최소 O(N!)인데 2중 for문까지 더하면 안 될 것 같아서 줄여보자

 1차원 배열 queen에 이 전까지 queen의 위치를 저장 -> for문 한 번으로 해결

 

(여기 2번째 코드에서 시간복잡도가 엄청나게 줄었음)

 

 

 

 

3번째 통과한 코드

 

 

📌 Idea : isSafe 는 줄일대로 다 줄여봤으니까 재귀 도는 횟수를 줄여보자 

 

이것저것 쓸데 없는 코드 빼고, for문으로 재귀 횟수를 조금이라도 줄임

 

(여기서는 조금밖에 안 줄었는데 다행히 통과함)

 

 

다른 사람들 푼 거 찾아보니까 비트마스킹 같은 걸로 풀었는데 이건 머리 아프니까 안 알아봤다. 끝~