[C#] 백준 15649번 문제풀이

문제번호: 15649

문제명: N과 M (1)

문제링크: https://www.acmicpc.net/problem/15649

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다.

 

오늘은 백트랙킹을 활용하는 문제를 풀이하겠습니다.

우선, 백트랙킹이란 무엇일까요?

백트래킹이란, 해를 찾는 도중 해가 절대 될 수 없다고 판단되면, 되돌아가서 해를 다시 찾아가는 기법을 말합니다.

또한 백트래킹은 재귀적으로 문제를 해결해야 합니다.

 

백트래킹은 모든 경우의 수에서 조건을 만족하는 경우의 수를 탐색하는 것 이기 때문에 BFS, DFS모두로 구현 가능합니다. 다만, DFS가 조건에 부합하지 않으면 되돌아간다는 성질에 더 걸맞기 때문에 DFS를 더 많이 이용합니다.

 

왼쪽부터 BFS(너비우선), DFS(깊이우선)

 

백트래킹 문제가 처음이기도 하고 DFS를 제대로 구현해 본 적도 없어서 막막했습니다.

그래서 백트래킹 유튜브 강좌를 찾게 되었습니다.

https://www.youtube.com/watch?v=atTzqxbt4DM

강사님이 친절히 설명해주셔서 백트래킹을 이해하는데 큰 도움이 되었습니다.

 

강좌를 시청한 후 강좌에 나온 기법으로 비슷하게 구현해 보았습니다.

강사님은 파이썬으로 구현하셨지만 제 언어는 C#이기 때문에 C# 문법에 맞게 코드를 작성하였습니다.

 

코드를 다 작성한 후에 제출해 보니 시간초과가 났는데, 경우의 수가 많아지다 보니 출력량이 많아져서 발생하는 시간초과였습니다. 그래서 간단하게 StreamReader, Writer를 사용해 주니 통과되었습니다.

 

백트래킹과 DFS라는 개념이 생소하여 이해하는데 시간이 좀 걸렸던 것 같습니다.

다음엔 이번 문제와 관련된 또 다른 문제로 백트래킹을 연습하는 시간을 가져야 될 것 같습니다.

감사합니다.

 

public static void Main()
{
    StreamReader sr = new StreamReader(Console.OpenStandardInput());
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int[] NM = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    int N = NM[0];
    int M = NM[1];

    Stack<int> rs = new Stack<int>();
    bool[] chk = new bool[N + 1];

    Recur(0);

    void Recur(int num)
    {
        if (num == M)
        {
            //Console.WriteLine(rs.ToString());
            foreach(int a in rs.Reverse())
            {
                sw.Write(a + " ");
            }
            sw.WriteLine();
            return;
        }

        for (int i = 1; i < N+1; i++)
        {
            if (chk[i] == false)
            {
                chk[i] = true;
                rs.Push(i);
                Recur(num + 1);
                chk[i] = false;
                if (rs.Count > 0)
                    rs.Pop();
            }
        }
    }

    sr.Close();
    sw.Close();
}