[백준] 9663번: N-Queen - python

문제보기

 

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

9663번: N-Queen

 

 

N에 따른 테스트케이스를 찾고 있다면 해당 사이트를 참고바란다!

https://ko.wikipedia.org/wiki/%EC%97%AC%EB%8D%9F_%ED%80%B8_%EB%AC%B8%EC%A0%9C

여덟 퀸 문제 - 위키백과, 우리 모두의 백과사전

 

 

 

---

 

풀이 & 코드

 

N이 4이상이라면 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓을 수 있다. 이때, 가능한 경우의 수를 구하는 문제이다. 필자는 2차원 보드를 이용한 문제이기 때문에 관성적으로 2차원 배열을 만들었다. N × N을 돌면서 처음 queen을 놓을 자리를 정해 dfs를 만들어 depth를 추가할 때마다 가능한 칸에 퀸을 놓고 check를 해 depth가 N이 될때 count하는 방법으로 진행했다. 하지만, 2차원 배열로 만드니 시간초과가 발생했다. 이후에 여러 수정을 해보았지만 결론적으로는 실패했다. 해당 포스팅은 다른 분들의 풀이를 보고 이해한 바를 적으려고 한다.

 

먼저 2차원 배열을 과감히 버렸다. 퀸은 가로, 세로 대각선을 공격한다. 다시말해 같은 row에 퀸이 두 개 들어갈 수 있다. 따라서 N 사이즈의 배열을 만들고 해당 배열의 index를 row_index, element를 column_index로 생각한다면 보다 적은 메모리를 사용하여 계산할 수 있다. 만일 N이 4인 문제에서 다음과 같이 퀸을 놓았다면 [1, 3, 2, 4]로  표현된다.

퀸
		퀸
	퀸
			퀸

 

 

 

자 이제 코드를 살펴보자.

 

 

전체적인 구성은 앞에서 말한바와 동일하게 dfs를 활용했다. dfs는 해당 depth 즉 해당 row의 몇 번째에 퀸을 놓을 지 판단하도록 작성했고, depth가 n이 되면 global 변수인 count에 1을 더해주고 return 하도록 작성했다. queens라는 1차원 배열에서 index는 row_index, value는 column_index을 나타낸다. 따라서 새로운 퀸을 놓을 때에는 queens[depth]에 column_index를 추가해 주었다. 퀸의 위치를 선정할 때에는 non_checked 배열을 이용해 기존에 선택되지 않은 column중에서 선택을 하였고 아래의 조건문을 통해 대각선에 겹치는 게 있는 지 판단했다. 참고로 abs는 절댓값을 계산하는 매서드이다.

if (depth - i) == abs(queens[depth] - queens[i]):
    break

 

 

 

 

---

 

후기

그동안 너무 뻔한 문제들만 풀어온 거 같다. 전체적으로 문제푸는 속도는 빨라졌지만 매번 같은 방식으로 풀 게 되는 경우가 많다. 정중지와라고 우물 안 개구리가 되어가는 거 같다. 생각의 틀을 깨야 하는데 이게 참 어렵다. 해당 문제는 2차원 문제면 2차원 배열을 구성해야 한다는 틀을 깨게 만든 문제이다. 물론... 비슷한 문제가 나와도 2차원으로 접근할 거 같긴 하지만 지금을 경험 삼아 1차원으로 바꾸어 푸는 생각도 할 수 있으면 좋겠다:)