[C#]백준 15649번: N과 M(1)

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

---

• 문제

---

• 문제풀이

백트래킹 문제이다. 깊이 탐색을 활용해서 풀어준다.

---

• 코드 1

using System.ComponentModel.Design;
using System.Text;

namespace ConsoleApp2
{
    internal class Program
    {
        static public StringBuilder sb = new StringBuilder();
        static public bool[] visited;
        static public int[] result;
        static void Main(string[] args)
        {
            
            
            string[] input = Console.ReadLine().Split();
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);
            result= new int[N];
            visited= new bool[N];
            
            
            dfs(N, M, 0);
            Console.WriteLine(sb.ToString());
        }
        static void dfs(int N, int M, int cnt)
        {
            if (cnt == M)
            {
                for(int i=0;i<M;i++)
                {
                    sb.Append(result[i]+" ");
                }
                sb.AppendLine();
                
            }
            for(int i=0;i<N;i++)
            {
                if (!visited[i])
                {
                    visited[i]=true;
                    result[cnt] = i + 1;
                    dfs(N, M, cnt+1);
                    visited[i] = false;
                }
            }
        }
    }
}

---

• 후기

DFS를 활용한 백트래킹 문제이다.