[알고리즘] 백트래킹(Backtracking)

---

<목차>

1. 백트래킹이란?

2. 백트래킹 예시(N-Queen)

---

1. 백트래킹이란?

: 제약된 조건을 가진 문제에서 답을 찾기 위한 방법.

 

- DFS 방식으로 확인(https://geukggom.tistory.com/66).

- 모든 경우의 수를 상태 공간 트리를 통해 표현해 탐색.

• Promising : 해당 루트가 제약된 조건에 맞는지 확인
• Pruning : 가지치기. Promising단계에서 조건에 맞지 않으면 바로 다른 루트로 가서 탐색 시간 절약.

 

* 상태 공간 트리(State Space Tree)

: 문제 해결 과정의 중간 상태를 Node로 나타낸 트리

&nbsp;출처 :&nbsp;쉽게 배우는 알고리즘 (문병로 저, 한빛아카데미, 2018)

---

2. 백트래킹 예시

백트래킹의 대표적인 문제 예시로는 N-Queen 문제가 있습니다.

 

* N-Queen : 크기가 N * N인 체스판 위에 퀸 N개를 서로 공격할 수 없도록 놓는 경우의 수를 구하는 문제.

https://ko.wikipedia.org/wiki/%EC%97%AC%EB%8D%9F_%ED%80%B8_%EB%AC%B8%EC%A0%9C

여덟 퀸 문제 - 위키백과, 우리 모두의 백과사전

 

* 풀이 방법 : GitHub (단, 체스판을 회전시켰을 때 겹치는 경우의 수를 고려하지 않음.)

 

public void nQueen(int n)
{
    List<int> answer = new List<int>();
    int row = 0;
    int column = 0;
    bool is_wrongColumn = false;
    while (true)
    {
        if(is_wrongColumn || column == n) //답이 나온 경우 + 현재 row에 배치할 column이 없는 경우
        {
            is_wrongColumn = false;
            column = answer[answer.Count - 1] + 1; //이전 행의 column+1을 가져옴
            row = answer.Count - 1; //이전 행의 row 가져옴
            if (row == 0 && column == n) return; //모든 경우의 수를 체크한 후, return
            answer.RemoveAt(answer.Count - 1); //list에 추가했던 이전 row를 지움
            continue;
        }
        if (is_available(answer, column)) //지금까지의 리스트에 현재 column이 맞는지 확인
        {
            answer.Add(column);
            row++;
            column = 0;
        }
        else column++;
        if (answer.Count == n) is_wrongColumn = true; 
    }
}


//이제까지 만든 리스트가 조건에 맞는지 확인 = Promising
public bool is_available(List<int> candidateList, int column)
{
    if (candidateList.Count < 1) return true; //리스트에 한개만 있을 때는 그냥 추가
    int row = candidateList.Count;
    for (int i = 0; i < row; i++)
    {
        //대각선일 때 || column 같을 때
        if (Mathf.Abs(candidateList[i] - column) == row - i
            || candidateList[i] == column) return false;
    }
    return true;
}