백준 C# - 15650 +)풀이

이 문제를 풀기 앞서 아래 문제를 먼저 풀고 오는 것을 추천한다.

백준 C# - 15649 +) 풀이

---

N과 M(1)과의 차이점은 뒤에 숫자들이 앞의 숫자들보다 커야한단느 것이다. 출력 예시를 보면 더 쉽게 이해할 수 있다.

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

---

N과 M() 주요 알고리즘

N과 M(1)과의 차이점은 매개변수 at이 추가된 것이다. 이는 재귀가 어디서부터 시작하는지 나타내는 변수이다.

public static void Dfs(int at, int depth)
{
    if(depth == M)
    {
        for (int i = 0; i<M;i++)
        {
            sb.Append(arr[i]).Append(' ');
        }
        sb.AppendLine();
        return;
    }   
    for(int i = at ;i<=N;i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            arr[depth] = i;
            Dfs(i, depth+1);
            visited[i] = false;
        }
    }
}

 

백트래킹문제는 알고리즘을 짠 다음 잘 이해가 안가는 부분이 있다면 실행과정을 직접 써보면서 이해하는게 도움이 많이 된다.

i = 3과 i = 4도 직접 써보는 것을 추천한다.

---

코드 전문

using System;
using System.Text;

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

            Dfs(1,0);
            Console.WriteLine(sb.ToString());
        }
    }
}