[알고리즘] 4주차 구현 (완전탐색, 백트래킹)

nerry·2022년 1월 26일

DPT 알고리즘

알고리즘

목록 보기

20/86

구현 : 완전 탐색

빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법
Brute-Force 라고도 부름. 문제 푸는 '방법'이다.

동작 과정

해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산
가능한 모든 방법을 다 고려
실제 답을 구할 수 있는지 적용

종류

순열 Permutation

완전 탐색의 대표적 유형. N!의 시간이 필요하기에 N이 한자리 수 일때만 완전탐색으로 할 수 있음

비트마스크

2진수를 이용하는 컴퓨터 연산을 이용하는 방식
문제에서 나올 수 있는 모든 경우의 수가 각각의 원소가 포함 되거나 포함되지 않는 두가지 선택으로 구성되는 경우 유용하게 사용 가능

재귀

문제를 만족하는 경우들을 만들어가는 방식
포함되거나 포함되지 않거나 두가지 선택을 가질 때 사용한다.

BFS/DFS

길 찾기 문제. 주로 완전탐색 + DFS/BFS 문제가 많이 나옴
조건을 처리할 추가적인 작업이 필요한 경우에 완전탐색으로 해결한 후에 이 방법을 적용하게 됨

Brute Force

반복/ 조건문을 통해 가능한 모든 case를 만들어 답을 구하는 방법

종류

선형 구조 : 순차 탐색 (전체적인 탐색)
비선형 구조 : DFS, BFS

백트래킹

"가능한 모든 방법을 탐색한다"
현재 상태에서 가능한 후보군으로 가지를 치며 탐색하는 알고리즘
분할 정복을 이용. 재귀함수를 이용하여 해를 찾아가는 도중 해가 되지 않는 경로가 있다면 더 이상 가지 않고 되돌아간다.

제약 조건 만족 문제에서 해를 찾기 위함
해를 찾기 위해 후보군에 제약 조건을 점진적으로 체크하다가 만족할 수 없다고 판단되면 즉시 backtrack( 다시는 이 후보군을 체크하지 않을 것을 명시), 다음 후보군으로 넘어가면서 결국에는 최적의 해를 찾는 방법
실제 구현시, 모든 경우의 수를 상태공간트리를 통해 표현
- 각 후보군을 DFS로 확인
- 트리를 탐색하면서 제약에 맞지 않으면 해의 후보가 될만한 곳으로 넘어가 탐색
  - Promising : 해당 루트가 조건에 맞는지 검사
  - Pruning 가지치기 : 조건에 맞지 않으면 포기하고 다른 루트로 가 탐색의 시간을 절약하는 기법

N Queen 대표적인 백트래킹 문제
N*N 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치

Pruning
- 한 행에 하나의 퀸
- 맨 위 행부터 퀸 배치, 다음 행에 이동할 수 없는 위치를 찾아 퀸 배치
- 앞선 행에 배치된 퀸에 의해 다음 행에 퀸들이 이동할 수 없는 위치일 겨우 더이상 그 퀸 배치를 이용하지 않고, 그 행의 퀸 배치를 바꿈
Promising
- 해당 루트가 조건에 맞는 지 검사하는 기법
- 여태 배치된 퀸이 이동할 수 없는 위치가 있는지를 조건으로 확인
  - 수직 체크 : 같은 열 다른 행 확인
  - 대각선 체크 : 열 Gap == 행 Gap 일 경우
  - 수평 체크는 한 행에 하나의 퀸만 고르면서 해결했음

[절차]

DFS 수행
유망한 노드 검토
방문한 노드를 포함해서 유망한 노드이면 서브트리로 이동, 그렇지 않으면 백트래킹 수행

3. 방문한 노드의 하위 노드로 이동 후 재귀를 통해 DFS 수행
4. 백트래킹 수행
방문한 노드를 Pruning하고 상위 노드로 백트래킹 후 다시 DFS 수행

n=int(input())
def is_available(candidate, current_col):
    current_row = len(candidate)
    for queen_row in range(current_row):
        if candidate[queen_row] == current_col or abs(candidate[queen_row] - current_col) == current_row - queen_row:
            # 수직 체크 : 같은 열에 있는지 없는지 / 대각선 체크 : 열 차이와 행 차이가 같으면 대각선에 위치한 것임
            return False
    return True


def DFS(N, current_row, current_candidate, final_result):
    if current_row == N: # n 행에 모든 queen을 찾았을 때
        final_result.append(current_candidate[:]) # [:] 얕은 복사
        return

    for candidate_col in range(N):
        if is_available(current_candidate, candidate_col): # 현재 행의 한 칸이 괜찮은지
            current_candidate.append(candidate_col) # 괜찮으므로 후보에 추가하고
            DFS(N, current_row + 1, current_candidate, final_result) # 다음 행으로 넘어가기
            current_candidate.pop() # 방금 후보 지우기


def solve_n_queens(N):
    final_result = []
    DFS(N, 0, [], final_result)
    return len(final_result)

print(solve_n_queens(n))