[Silver III] N과 M (2) - 15650

문제 링크

성능 요약

메모리: 5660 KB, 시간: 52 ms

분류

백트래킹

제출 일자

2025년 12월 2일 18:26:56

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

제출코드

// 순열 생성
// depth 있는 dfs로 가능할듯
// m개만큼 최대 depth 조건 설정, 1~n중에 현재보다 큰 수들 전부로 dfs호출

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;

namespace algorithm_study
{
    class main
    {
        static int N,M;
        static int[] sequence;
        public static void Main(String[] args)
        {
            string[] input = Console.ReadLine().Split();
            N = int.Parse(input[0]);
            M = int.Parse(input[1]);
            sequence = new int[M];
            for (int i = 1; i <= N; i++)
            {
                DFS(i, 1);
            }

            return;
        }

        public static void DFS(int n, int depth) { 
            sequence[depth-1] = n;
            if (depth == M)
            {
                Print();
                return;
            }
            for (int i = n + 1; i <= N; i++)
            {
                DFS(i, depth + 1);
            }
        }

        public static void Print()
        {
            Console.WriteLine(string.Join(" ",sequence));
        }
    }
}

설명

순열을 구하면 되기 때문에, 간단하게 DFS에서 현재 n보다 큰 n+1~N 까지 DFS를 재귀적으로 호출하도록 구현하였다. 만약 조합을 구하려고 한다면, 방문여부 visited배열을 활용해서 백트래킹을 구현해야할 것이다.

가독성 개선

현재 풀이에서는 DFS 호출 후 현재 depth-1 위치에 n을 결정하고 있는데, 호출 직전에 배열에 데이터를 삽입해주면 더 깔끔하게 만들 수 있었다.

// ...
namespace algorithm_study
{
    class main
    {
        static int N,M;
        static int[] sequence;
        public static void Main(String[] args)
        {
            string[] input = Console.ReadLine().Split();
            N = int.Parse(input[0]);
            M = int.Parse(input[1]);
            sequence = new int[M];
            DFS(1, 0); // 한번의 호출로도 가능
            return;
        }

        public static void DFS(int n, int depth) { 
            if (depth == M)
            {
                Print();
                return;
            }
            for (int i = n; i <= N; i++) // i를 n부터 시작하게 바꿈으로써 dfs를 n=1 호출했을때 첫번째 인자로 모든 수를 가지는 경우의 수를 만들 수 있다.
            {
                sequence[depth] = i; // dfs호출전에 배열에 데이터를 삽입하도록 개선,, 함수 내부에서는 증가된 depth를 선판단하도록
                DFS(i + 1, depth + 1);
            }
        }

        public static void Print()
        {
            Console.WriteLine(string.Join(" ",sequence));
        }
    }
}