백준 C# - 15649 +) 풀이

대표적인 백트래킹 문제이다. 

백트래킹

모든 경우의 수를 탐색하며 더 이상 해가 나올 것 같지 않으면 이전으로 돌아가서 다른 경우를 탐색한다.

---

풀이

원래 알던 DFS 알고리즘에서는 visited[i] = true만 있었는데 백트래킹에서는 visited[i]=false가 추가된다. 처음에는 이부분이 이해하기가 몹시 어려웠다.

if(depth == M)
{
    for (int i = 0; i < M; i++)
    {
        sb.Append(arr[i]).Append(' ');
    }
    sb.AppendLine();
    return;
}
for(int i = 1; i <= N;i++)
{
    if(!visited[i])
    {
        visited[i] = true;
        arr[depth] = i;
        DFS(depth + 1); // 다음 자식 노드 방문을 위해 depth + 1
        visited[i] = false; //백 트래킹 : 이전에 사용한 숫자를 사용 가능 하도록 하여 되돌아감
    }
}

콘솔창에 추가하면서 이부분을 이해하려고 노력했는데 도저히 이해가되지 않아서 아래와 같이 작성하면서 이부분이 어떻게 작동하는지 간신히 이해했다. 이해가 잘 안된다면 직접 쓰면서 이해하는게 제일 좋은 방법인 것 같다.

---

코드 전문

using System;
using System.Text;
namespace baek2
{
    class Program
    {
        static int M,N;
        static bool[] visited = new bool[9];
        static int[] arr = new int[9];
        static StringBuilder sb = new StringBuilder();

        static void DFS(int depth)
        {
            if(depth == M)
            {
                for (int i = 0; i < M; i++)
                {
                    sb.Append(arr[i]).Append(' ');
                }
                sb.AppendLine();
                return;
            }
            for(int i = 1; i <= N;i++)
            {
                if(!visited[i])
                {
                    visited[i] = true;
                    arr[depth] = i;
                    DFS(depth + 1);
                    visited[i] = false; //백 트래킹 : 이전에 사용한 숫자를 사용 가능 하도록
                }
            }
        }
        public static void Main()
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            N = input[0];
            M = input[1];

            DFS(0);
            
            Console.Write(sb.ToString());
        }
    }
}