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

문제링크

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

15649번: N과 M (1)

 

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

조건

시간제한 : 1초
메모리 제한 : 512 MB

입력

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

출력

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

 

문제정리

1. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
2. 중복 되는 수열을 여러 번 출력하면 안됩니다.
3. 수열은 사전 순으로 증가하는 순서로 출력해야합니다.
4. 백트래킹 문제 

이번 문제의 경우 M개의 수열을 쭈욱 출력해주는 문제인데, 백트래킹으로 풀이를 하라고 하여

오랜만에 DFS과 백트래킹 문제를 찾아보고 공부를 한 후에 문제 풀이를 진행하엿습니다.

 

각 숫자는 딱 한번만 사용 되므로 bool 형인 visited 변수를 선언 하였으며 이 변수에는 숫자를 방문 하였는지 저장 하였습니다.

각각의 숫자를 1부터 하나씩 뽑아가며 visited가 M만큼 즉 count가 M만큼 될 때까지 돌다가 출력 해주는 재귀 함수를 이용하였습니다.

 

솔직히 이번 문제는 백트래킹의 기초라는데,, 많은 시간을 할애하여 문제를 풀 수 있었습니다.

다음에도 백트래킹과 DFS 관련하여 문제를 더풀어보고 익숙해져야 할 것 같습니다.

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    int N = int.Parse(input[0]);
    int M = int.Parse(input[1]);
 
    int[] result = new int[9];
    bool[] visited = new bool[9];
 
    DFS(0);
 
    writer.Close();
    reader.Close();
 
    void DFS(int count)
    {
        if (count == M)
        {
            // 카운트가 M만큼 된다면 출력 
            for (int i = 0; i < M; i++)
                writer.Write($"{result[i]} ");
            writer.WriteLine();
        }
        else
        {
            for (int i = 1; i <= N; i++)
            {
                // 뽑은 숫자의 방문 유무를 저장
                if (!visited[i])
                {
                    visited[i] = true;
                    result[count] = i;
                    DFS(count + 1);
                    visited[i] = false;
                }
            }
        }
    }
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.