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

문제번호: 15654

문제명: N과 M (5)

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

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

 

오늘은 N과 M (5)번 DFS(깊이우선탐색)와 백트래킹을 이용하는 문제를 풀었습니다. 평소 BFS와 DFS에 많이 약하고 이해를 못 했었는데 이번 문제를 통해서 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);
    List<int> Nums = Array.ConvertAll(sr.ReadLine().Split(), int.Parse).ToList();
    Nums.Sort();
    int N = NM[0]; // 4
    int M = NM[1]; // 2

    bool[] visited = new bool[N];
    int[] result = new int[M];

    DFS(0);

    void DFS(int depth)
    {
        if (depth == M)
        {
            for (int i = 0; i < M; i++)
            {
                sw.Write(result[i] + " ");
            }
            sw.WriteLine();

            return;
        }

        for (int i = 0; i < N; i++)
        {
            if (visited[i] == true) continue;

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

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