N-Queen
-
[백준] N-Queen 9663번알고리즘/백준 2021. 9. 7. 18:35
문제 링크 풀이 대표적인 백트래킹 문제라고 합니다. 백트래킹이란 깊이 우선 탐색 중에 오답을 만나면 이전 분기점으로 돌아가는 걸 말합니다. 재귀함수를 호출할 때 특정 조건일 때만 함수를 호출합니다. 트리로 봤을 때, 이전 분기점으로 돌아가 하위 노드가 구성되지 않은 모습을 가지치기라고도 합니다. 이 문제는 일차원 배열로 풀 수 있습니다. 문제를 보면 N x N 크기의 체스에 N개를 놓는 것이기 때문에 조건을 만족하는 경우의 수는 무조건 한 행에 하나의 퀸이 있어야 하기 때문에, 다음과 같이 표현할 수 있습니다. rows[0] = 1 // 0번째 행의 1열에 퀸 놓기 퀸을 위치시키는 규칙을 말하기 전에 재귀함수의 탈출조건부터 살펴보겠습니다. 재귀함수는 반드시 탈출 조건이 있어야 하는데요. 그 탈출 조건이란..