[백준][C#] 15649 N과 M (1) - 실버3

문제 보기

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

15649번: N과 M (1)

 

 

문제

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

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

 

 

입력

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

 

 

출력

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

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

 

 

 

실버3 문제를 풀다가 마주친 N과 M 시리즈...

한 문제만 풀 줄 알면 전부 우려먹기가 가능한 엄청난 혜자 문제들이다.

 

 

우선 이 문제를 풀 때는 DFS와 백트래킹을 사용하는 것이 일반적이다.

예제 입출력을 살펴보자

 

예제 입력 1

3 1

예제 출력 1

1
2
3

 

예제 입력 2

4 2

예제 출력 2

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

 

주어진 수열은 [1, 2, 3]

이것을 1개씩 뽑을 때의 순열을 모두 나열하면 된다.

 

방법은 간단하다.

예제 2번로 예를 들어본다.

반복문을 M중첩으로 돌리면서 전부 출력하면

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

이렇게 나올 것이다.

중복되는 수는 있을 수 없으니 이미 뽑은 index라면 continue하면 된다.

 

M이 사전이 주어진 정보라면 반복문 두 번을 돌리는 간단한 문제지만,

입력으로 주어지기 때문에 Depth(M)만큼 재귀를 돌려야 한다.

 

1 - 1' 2' 3' 4'

2 - 1' 2' 3' 4'

3 - 1' 2' 3' 4'

4 - 1' 2' 3' 4'

 

이렇게 연결 된 그래프를 깊이 우선 탐색을 돌린다고 생각하면 이해가 쉽다.

// list에 이번 줄의 수열을 담아 놓는 것.
void DFS(bool[] visited, int[] list, int depth)
{
	// 마지막 depth에 도달하면
    if (depth == m)
    {
        StringBuilder stringBuilder = new StringBuilder();
        // list에 담아둔 수열을 출력.
        for(int i = 0; i < m; i++)
        	stringBuilder.Append(list[i] + " ");
        Console.WriteLine(stringBuilder.ToString());

        return;
    }
    for (int i = 1; i <= n; i++)
    {
    	// 이 index를 이미 방문했다면? (1 1과 같이 중복되는 수열은 순열이 아님)
        if (!visited[i])
        {
        	// 방문한 index는 true로
            visited[i] = true;
            // list[depth]에 이번 index를 담는다.
            list[depth] = i;
			// 다음 depth 재귀
            DFS(visited, list, depth + 1);
			
            // 다음 줄의 수열을 작성하기 위해 false로
            visited[i] = false;
        }
    }
}

 

전체 코드

        static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            string input = reader.ReadLine();
            int n = int.Parse(input.Split()[0]);
            int m = int.Parse(input.Split()[1]);

            int[] list = new int[m];
            bool[] visited = new bool[n+1];
            DFS(visited, list, 0);

            void DFS(bool[] visited, int[] list, int depth)
            {
                if (depth == m)
                {
                    StringBuilder stringBuilder = new StringBuilder();
                    for(int i = 0; i < m; i++)
                        stringBuilder.Append(list[i] + " ");
                    print.WriteLine(stringBuilder.ToString());

                    return;
                }
                for (int i = 1; i <= n; i++)
                {
                    if (!visited[i])
                    {
                        visited[i] = true;
                        list[depth] = i;

                        DFS(visited, list, depth + 1);

                        visited[i] = false;
                    }
                }
            }
        }