N-Queen 알고리즘

N-Queen 알고리즘을 풀다가 backtracking의 대표적인 문제여서 정리한다. 여기 문제를 풀다가🤓

N-Queen 문제

8*8 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제이다. 퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다. 이 문제의 한가지 정답은 아래 그림과 같다. 이 문제의 조금 더 일반화된 문제는 Franz Nauck이 1850년에 제기했다. N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇가지가 있을까? N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

Backtracking = DFS (모든 경우의 수 탐색) + 가지치기 (확률이 없는 경우 제외)

정리가 무색할 정도로 별거 없다! 너무 옛날에 썼다가 그냥 포스팅하는 거고 어차피 이 블로그는 내 일기장 같은 것이니…

keypoint라고 생각이 드는 건, queen이 있다고 체크하고 그 상태에서 available하다 를 판단할 때, 체스판이기 때문에 n*n의 배열에 퀸의 위치표시를 해야 한다고 생각하지만 n배열로 해결할 수 있다는 점이다.

n배열로 퀸의 위치를 체크하는 것은, n배열의 index값을 row값으로 생각하고 value값을 column 값으로 생각하는 것이다.

이 포인트만 잘 기억하고, DFS가 전체 탐색하는 것(?)의 일환이기 때문에 recursive와 for문을 사용한다는 점을 기억해야 할 것 같다.

💭 항상 알고리즘을 풀 때, 이건 시간이 너무 많이 걸리지 않나? 시간복잡도가 어떻게 되지? 이런 생각을 하다보면 문제를 제대로 못 풀때가 많은 것 같다. 최근에 들은 특강에서 제일 공감한 것 중에 하나가, 배경지식, 문제해결능력, 구현력이 필요하다는 것이다. 셋 다 부족하지만 특히 나에게 부족하다고 생각이 드는 건 구현력이다. 슬프다 어찌됐건 구현력이 필요할 땐 20~30분 고민해보고 안풀리면 풀이를 보고서라도 어떻게든 구현할 수 있는 능력이 돼야 한다는 것이다. 그래서 그렇게 해보려고:D!

쓰다보니 N-Queen문제보단 어떻게 공부를 해나가야 할 것인가에 대한 것 같다.