backtracking

[프로그래머스] Lv.2 N-queen (DFS) + 연습용 체스판

N-queen queen 을 겹치지 않게 놓는 문제이다. 시간복잡도는, 모든 row 에서 모든 column 에 대해 검사하므로, O(N^N) 이다. 풀이 코드 구조 queen 을 놓기 전에, 이전 queen 들의 위치와 비교하여 놓아도 되는지 검사한다. 되면 queen 을 놓는다 (함수 호출, DFS 탐색) 안되면 더 이상 함수호출을 하지 않는다 (끝 = 가지치기) 가지치기는 어떻게 되는가 check 함수에서 여기(newRow, newCol) 에 queen 을 놔도 되는지 검사를 한다. 이때 queen 을 놓아도 된다고 판단되면 계속해서 함수 호출을 하고 (DFS 탐색), queen 을 놓으면 안된다고 판단되면 거기서 끝낸다. 따라서 그 상태에서는 더 이상의 함수 호출이 없으므로, 가지치기가 된다. qu..