[BAEKJOON] 백준 10974: 모든 순열 (C#)

문제 링크

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

 

 

문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 

 

 

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

 

 

 

통과한 답안

namespace _10974
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            List<int> numbers = new List<int>();
            bool[] used = new bool[N];
            GeneratePermutations(N, numbers, used);
        }
        
        static void GeneratePermutations(int n, List<int> numbers, bool[] used)
        {
            if (numbers.Count == n)
            {
                Console.WriteLine(string.Join(" ", numbers));
                return;
            }

            for (int i = 0; i < n; i++)
            {
                if (!used[i])
                {
                    used[i] = true;
                    numbers.Add(i + 1);
                    GeneratePermutations(n, numbers, used);

                    numbers.RemoveAt(numbers.Count - 1);
                    used[i] = false;
                }
            }
        }
    }
}

 

숫자 N이 주어지는 경우, 1부터 N까지의 수로 이루어진 순열을 사전 순으로 출력하는 문제이다.

문제를 어떻게 풀이해야될지 감이 안오다가 알고리즘 분류에 있는 백트래킹을 보고 풀이할 수 있었다.

 

N을 입력 받은 후에 순열을 만들 List를 생성하고

백트래킹에 이용할 bool 값을 생성한다.

 

이후에 GeneratePermutations라는 메서드를 만들어서

number의 길이가 N이라면 해당 순열을 출력하도록 하고

그렇지 않다면 for문을 이용하여 사용하지 않은 수를 이용하여

List에 해당 숫자를 추가하고 사용한 것으로 체크하고

재귀적으로 메서드를 불러와서 다음 숫자를 선택하도록 한다.

이후에 마지막 숫자를 제거하고 사용하지 않은 상태로 변경하여 다음 순열을 만든다.