[C#]백준 15652번: N과 M(4)

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

15652번: N과 M (4)

---

• 문제

---

• 문제풀이

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

---

• 코드 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, 1);
            Console.WriteLine(sb.ToString());
        }
        static void dfs(int N, int M, int cnt, int num)
        {
            if (cnt == M)
            {
                for(int i=0;i<M;i++)
                {
                    sb.Append(result[i]+" ");
                }
                sb.AppendLine();
                return;
            }
            for(int i=num;i<=N;i++)
            {
                //if (!visited[i])
                //{
                //    visited[i]=true;
                    result[cnt] = i;
                    dfs(N, M, cnt+1, i);
                //    visited[i] = false;
                //}
            }
        }
    }
}

---

• 후기

백트래킹에 dfs를 변형해서 할 수 있다.