[백트래킹] 백준 N-Queen 문제에 대한 고찰, python

🤔 왜 최적화를 못했을까?

백트래킹 대표적인 문제로 백트래킹 구현도 중요했지만, 최적화가 더욱 중요한 문제였다.
Pypy3로도 시간초과가 나서 여러 고민을 해보았지만, 방법이 전혀 떠오르지 않았다.
내 생각은 단순하게 반드시 전체 탐색을 해서 전에 탐색한 다음 로우부터 col들을 하나씩 뒤지면서 찾아 내는 것이었다.

그렇게 할 때에 시간 복잡도는 어느정도 였을까 계산을 해보면, O(n*3^n)이라는 시간 복잡도(심지어 대각선 노드도 따로 하나씩 확인했음)를 가지고 있어서 통과를 못했다...
Pypy라면 어떻게든 시간 제한이 10초니까 해줄거야.. 라는 믿음도 안통했다 ㅠ

그래서 가만히 모니터만 들여다 보면서 어떻게 최적화 하지? 어떻게 하지? 하염없이 고민만 했던 것 같다.
아이디어가 전혀 떠오르지 않아 답안을 이것저것 봤다.

백트래킹을 그대로 사용하면서 O(2^n)으로 풀 수 있는 답안을 찾았다. 코드도 간결하고 바로 이해가 가능한 좋은 코드와 풀이었다.

풀이를 보니 나는 풀 때 대각선에서 발견되는 공통점을 찾지 못했는데 대각선을 계산할 때에 '/'이런 방향과 '\' 다른 방향의 차이가 없을 것이라 생각했지만 아니였다.

♟ 퀸의 개수는 결국 row index 또는 col index 와 동일하다

정말 중요한 포인트였다. 겹치는 것이 있다는 것은 반복을 줄일 수 있다는 것이니까, 원래 내가 작성한 코드라면 퀸의 개수에 관련된 정보는 처음 퀸의 갯수만 확인하고 전혀 쓰임이 없었다. 하지만 문제의 특성상 퀸은 row 또는 column당 하나씩만 존재 할 수 있기 때문에 결국 퀸의 개수는 row의 index와 다를 게 없다. 결국 2중 for문을 사용하지 않고서도 문제를 풀 수 있다.

조합을 구할 때 문제처럼 여태까지 들어간 인덱스를 기준으로 계산하는 것을 퀸의 개수로 해결하는 방법으로 해결한 것이다.

🏁 대각선을 해결하자

나는 처음 구상할 때에 row와 column만 체크하고 대각선을 어떻게 처리할지 떠올리지 못해 단순히 반복문을 통해 check된 곳과 지금 현재 위치의 차이가 같다면 대각선 위치에 놓여 있다고 생각을 해, 매번 반복문을 통해 확인을 했다.

하지만 '/' 이런 오른쪽으로 기운 쪽의 기록을 기록하는 것과 '\' 이런 방향에 따른 확인하는 배열 두개를 따로 선언하고 두개 다 포함되지 않을 때 선택 당하는 것을 둘 다 만족 시킬 때, 그곳에 퀸을 배치하는 방법으로 확인하는 것이다. '/' 모양의 그래프는 특이하게도 (r,c)일 때 두 개를 더한 값이 항상 같기 때문에 (0,1) 과 (1,0) 이 대각선에 위치해 있다는 것을 쉽게 만족한다.
'\' 의 패턴은 살짝 더 복잡했는데 주어진 n에 대해서 r-c 였다. 하지만 배열을 음수로 찾기란 귀찮은 작업이기 때문에 간단하게 n-1을 더해주는 것으로 해결했다.

처음에 식을 보고선 이해가 잘 안되서 그림으로 따로 그려보고 이해 했다. 아이패드로 체스판을 가져와서 그리고 각각 left right 값을 그리는 식으로 확인했다.

'\' 모양의 값들 빨간색이 '/' 모양의 값은 파랑색으로 생각하면 좋겠다. 이런식으로 일정한 패턴이 생긴다.

😭 사람은 똑같은 실수를 반복한다

처음 풀때에는 그저 정답맞기에 집중해서 정확한 이해 없이 넘어가니 다음에 또 같은 문제를 풀지 못했다..

나는 자꾸 조합문제도 순열 문제처럼 코드를 작성해 버릇해서 정말 코드 효율이 자주 떨어지는 것 같다. 앞으로는 이 부분을 조금 더 염두하고 코드를 작성해야겠다.

그래서 이번에는 이것을 바로 어떻게 떠올릴까 고민을 많이 해보았다. 우선은 케이스를 나누는 것에 좀 익숙해져야 겠다는 생각이 많이든다. 대각의 방향을 고민 없이 무작정 다르다고 생각하고 패턴이 없다고 생각했지만, 아니였다. 작은 단위로 나누어서 해결하는 것이 PS에서 참 중요하다고 느꼈다.

또 느낀 것은 아무리 무식하게 다 계산하는 브루트 포스지만, 조금만 응용해서 나오게 되면 다양하게 최적화 할 수 있는 방법이 있다는 것을 다시 한번 깨닫는 시간이었다. 두 번째 푸는 것이지만 다음에 다시 풀었을 때 내가 오늘 배운 것을 적용해서 풀 수 있게 블로그에 남기려고 한다. 남은 문제들도 계속 고찰하면서 다시 한번 풀어봐야 겠다.

내가 수정한 코드와 그 전 코드는 밑 링크에 있다.
https://github.com/Deserve82/KK_Algorithm_Study/blob/master/Kangho/BOJ_9663.py