[백준 15654] N과 M (5) (C#, C++) - soo:bak

문제 링크

15654번 - N과 M (5)

설명

서로 다른 N개의 자연수가 주어지는 상황에서 N과 M (1 ≤ M ≤ N ≤ 8)이 주어질 때, 그중 M개를 중복 없이 고른 모든 수열을 사전 순으로 출력하는 문제입니다.

접근법

주어진 N개의 수 중에서 M개를 중복 없이 고르는 모든 순열을 생성해야 하므로 백트래킹을 사용합니다.

입력받은 수를 정렬한 후 백트래킹을 수행하면 사전 순 출력이 보장됩니다.

방문 배열로 이미 선택한 수의 인덱스를 표시하여 중복 선택을 방지합니다.

각 단계에서 아직 선택하지 않은 수 중 하나를 선택하고 방문 표시를 한 후 다음 단계로 진행합니다.

예를 들어 수 [9, 7, 8, 5]에서 M=2일 때 정렬 후 [5, 7, 8, 9]가 되고:

• 5 선택 → 7, 8, 9 중 선택 → (5, 7), (5, 8), (5, 9) 생성
• 7 선택 → 5, 8, 9 중 선택 → (7, 5), (7, 8), (7, 9) 생성
• 8 선택 → 5, 7, 9 중 선택 → (8, 5), (8, 7), (8, 9) 생성
• 9 선택 → 5, 7, 8 중 선택 → (9, 5), (9, 7), (9, 8) 생성

M개를 모두 선택하면 수열을 출력하고 백트래킹으로 돌아가 방문 표시를 해제합니다.

---

Code

C#

using System;
using System.Text;

namespace Solution {
  class Program {
    static int n, m;
    static int[] nums = new int[8];
    static int[] pick = new int[8];
    static bool[] used = new bool[8];
    static StringBuilder sb = new StringBuilder();

    static void Dfs(int depth) {
      if (depth == m) {
        for (var i = 0; i < m; i++)
          sb.Append(pick[i]).Append(' ');
        sb.Append('\n');
        return;
      }

      for (var i = 0; i < n; i++) {
        if (used[i]) continue;
        used[i] = true;
        pick[depth] = nums[i];
        Dfs(depth + 1);
        used[i] = false;
      }
    }

    static void Main(string[] args) {
      var first = Console.ReadLine()!.Split();
      n = int.Parse(first[0]);
      m = int.Parse(first[1]);

      var line = Console.ReadLine()!.Split();
      for (var i = 0; i < n; i++)
        nums[i] = int.Parse(line[i]);
      Array.Sort(nums, 0, n);

      Dfs(0);

      Console.Write(sb.ToString());
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[8];
int pick[8];
bool used[8];
ostringstream out;

void dfs(int depth) {
  if (depth == m) {
    for (int i = 0; i < m; i++)
      out << pick[i] << (i + 1 == m ? "\n" : " ");
    return;
  }

  for (int i = 0; i < n; i++) {
    if (used[i]) continue;
    used[i] = true;
    pick[depth] = arr[i];
    dfs(depth + 1);
    used[i] = false;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> arr[i];
  sort(arr, arr + n);

  dfs(0);
  cout << out.str();

  return 0;
}