백준 C# - 15651 +) 풀이

N과 M(3)번 문제이다.

만약 N과 M(1)과 N과 M(2)번을 풀고 왔으면 쉽게 풀 수 있다.

예제 출력을 보면 모든 조합이 다 출력되는 것을 확인할 수 있다. (아래 참조)

1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

 

---

N과 M(1)번 알고리즘 살펴보기

앞서 N과 M(1)번에서는 자릿수에 같은 숫자가 연속으로 오지 않게하는 문제였는데 여기에서 이를 적용하기 위해 방문표시를 했는데 여기에서 방문부분을 없애게 되면 전체 조합을 구할 수 있게 된다.

if(!visited[i])
{
    visited[i] = true;
    arr[depth] = i;
    DFS(depth + 1);
    visited[i] = false;
}

---

전체 조합의 경우를 구하는 알고리즘

그러므로 우리의 정답 알고리즘은 아래와 같다.

arr[depth] = i;
Dfs(depth+1);

---

코드 전문

using System;
using System.Text;

namespace baek2
{
    class Program
    {
        static int N, M = 0;
        static StringBuilder sb = new StringBuilder();
        static int[] arr = new int[9];
        
        public static void Dfs(int depth)
        {
            if(depth == M)
            {
                for (int i = 0; i<M;i++)
                {
                    sb.Append(arr[i]).Append(' ');
                }
                sb.AppendLine();
                return;
            }   
            for(int i = 1;i<=N;i++)
            {
                arr[depth] = i;
                Dfs(depth+1);
            }
        }
        public static void Main()
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            N = input[0];
            M = input[1];

            Dfs(0);
            Console.WriteLine(sb.ToString());

        }
    }
}