[BOJ][C#] 5568 카드 놓기

📕 문제

📌 링크

📗 접근 방식

• 백트래킹을 사용하여 카드의 모든 가능한 조합을 생성합니다.
• 중복된 조합을 방지하기 위해 HashSet을 사용합니다.
• DFS 함수
  • 뽑은 카드의 개수가 k와 일치하면 현재까지의 조합을 HashSet에 추가하고 종료
  • 뽑은 카드의 순서에 따라 조합이 중복되지 않도록 used 배열을 사용

기본적인 백트래킹 문제였던 것 같다.

📘 코드

namespace BOJ_5568
{
    class Program
    {
        static int n, k;
        static List<int> cards = new List<int>();
        static bool[] used;
        static HashSet<string> hashSet = new HashSet<string>();

        static void Main()
        {
            using StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            using StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

            n = int.Parse(sr.ReadLine());
            k = int.Parse(sr.ReadLine());

            for (int i = 0; i < n; i++)
            {
                cards.Add(int.Parse(sr.ReadLine()));
            }

            used = new bool[n];

            DFS(0, "");

            sw.Write(hashSet.Count);

            sr.Close();
            sw.Flush();
            sw.Close();
        }

        static void DFS(int idx, string str)
        {
            if (idx == k)
            {
                hashSet.Add(str);

                return;
            }

            for (int i = 0; i < n; i++)
            {
                if (used[i] == false)
                {
                    used[i] = true;
                    DFS(idx + 1, str + cards[i]);
                    used[i] = false;
                }
            }
        }
    }
}

📙 오답노트

📒 알고리즘 분류

• 자료 구조
• 브루트포스 알고리즘
• 해시를 사용한 집합과 맵
• 백트래킹