백트래킹

백트래킹?

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다.

 

 

연습 문제

 

1. 백준 15649 : https://www.acmicpc.net/problem/15649

using System.Text;

var input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int n = input[0], m = input[1];
int[] arr = new int[10];
bool[] isUsed = new bool[10];
StringBuilder sb = new StringBuilder();

void method(int k)
{
    if(k == m)
    {
        for (int i = 0; i < m; i++)
        {
            sb.Append(new string(arr[i] + " "));
        }
        sb.Append('\n');
        return;
    }
    for(int i = 1; i <= n; i++) //백트래킹 핵심
    {
        if (!isUsed[i])
        {
            arr[k] = i;
            isUsed[i] = true;
            method(k + 1);
            isUsed[i] = false;
        }
    }
}
method(0);
Console.WriteLine(sb.ToString());

 

백트래킹의 핵심이라 주석을 작성해둔 부분의 for문은 최대한 외우는 편이 좋을 것 같다.

나중에 시간이 된다면 N과M 시리즈를 모두 풀어보고자 한다.

 

2. 백준 9663 : https://www.acmicpc.net/problem/9663

var n = int.Parse(Console.ReadLine());

bool[] isUsed1, isUsed2, isUsed3;

int count = 0;

void SolveNQueens(int cur)
{
    if (cur == n)
    {
        count++;
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (!isUsed1[i] && !isUsed2[cur + i] && !isUsed3[cur - i + n - 1])
        {
            isUsed1[i] = isUsed2[cur + i] = isUsed3[cur - i + n - 1] = true;
            SolveNQueens(cur + 1);
            isUsed1[i] = isUsed2[cur + i] = isUsed3[cur - i + n - 1] = false;
        }
    }
}

isUsed1 = new bool[n];
isUsed2 = new bool[2 * n - 1];
isUsed3 = new bool[2 * n - 1];

SolveNQueens(0);
Console.WriteLine(count);

 

 

3. 백준 1182 : https://www.acmicpc.net/problem/1182

 

var input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
var input2 = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
var n = input[0];
var s = input[1];
int count = 0;

void Solve(int cur, int total)
{
    if(cur == n) {if(total == s) count++; return;}
    Solve(cur+1, total);
    Solve(cur+1, total + input2[cur]);
}

Solve(0, 0);
if(s == 0) count--;
Console.WriteLine(count);