백준 15649 C#) N과 M (1)

백트래킹 및 DFS의 기본을 익힐 수 있는 문제.

시리즈가 굉장히 많으므로 틈틈이 하나씩 풀면 좋다.

 

class Program
{
    static StreamWriter sw = new(new BufferedStream(Console.OpenStandardOutput()));

    static int n, m;
    static int[] result;
    static bool[] visited;

    static void DFS(int depth)
    {
        if (depth == m)
        {
            sw.WriteLine(string.Join(' ', result));
            return;
        }

        for (int i = 1; i <= n; i++)
        {
            if (!visited[i])
            {
                visited[i] = true;
                result[depth] = i;

                DFS(depth + 1);
                visited[i] = false;
            }
        }
    }

    static void Main()
    {
        string[] nm = Console.ReadLine().Split();

        (n, m) = (int.Parse(nm[0]), int.Parse(nm[1]));
        result = new int[m];
        visited = new bool[n + 1];

        DFS(0);
        sw.Close();
    }
}

 

 

백트래킹 문제들은 일단 DFS를 작성하고 시작한다.

그리고 DFS에 조건 분기를 덧붙여서 필요없는 가지를 치는데, 이 문제에서는 중복되는 수가 나오는 가지를 쳐야 한다.

따라서 bool 배열을 통해 사용된 수를 기억하고, 재사용하지 않도록 if문을 통해 확인해주면 되겠다.

사전 순은 따로 신경쓸 필요가 없다. for문을 여러번 거치면서 알아서 사전 순으로 완성되기 때문이다.

 

아래는 백트래킹의 과정을 그림으로 표현한 것이다.

 

난이도가 높아질 수록 조건 분기가 복잡해지고 노드가 가지는 의미가 비대해진다.

예를 들면, 이 문제처럼 단순 숫자가 아니라 다차원 배열을 나타낼 수도 있고, 특정 객체의 상태를 나타낼 수도 있다.

그래도 풀이가 정형화되어 있어 나름 도전해볼 만한 알고리즘이라고 할 수 있다.