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

문제 링크

15649번 - N과 M (1)

설명

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

접근법

1부터 N까지의 수 중에서 중복 없이 M개를 선택하는 순열(Permutation) 문제입니다.

백트래킹을 사용하여 모든 가능한 수열을 생성합니다.

백트래킹은 재귀적으로 선택지를 탐색하면서 조건을 만족하지 않으면 이전 상태로 돌아가는 방법입니다.

현재 깊이에서 1부터 N까지의 수를 순회하며:

1. 아직 사용하지 않은 수를 선택
2. 해당 수를 사용 중으로 표시
3. 다음 깊이로 재귀 호출
4. 재귀에서 돌아온 후 사용 중 표시를 해제 (백트래킹)

깊이가 M에 도달하면 하나의 완성된 수열이므로 출력합니다.

예를 들어 N = 3, M = 2일 때:

• 1 선택 → 사용 표시 → 다음 깊이
  • 2 선택 → 깊이 2 도달 → “1 2” 출력
  • 3 선택 → 깊이 2 도달 → “1 3” 출력
• 1 사용 해제 → 2 선택 → 사용 표시 → 다음 깊이
  • 1 선택 → 깊이 2 도달 → “2 1” 출력
  • 3 선택 → 깊이 2 도달 → “2 3” 출력
• 2 사용 해제 → 3 선택 → 사용 표시 → 다음 깊이
  • 1 선택 → 깊이 2 도달 → “3 1” 출력
  • 2 선택 → 깊이 2 도달 → “3 2” 출력

결과: 1 2, 1 3, 2 1, 2 3, 3 1, 3 2 (총 6개 = 3P2)

1부터 순서대로 탐색하므로 자동으로 사전 순으로 출력됩니다.

---

Code

C#

using System;
using System.Text;

namespace Solution {
  class Program {
    static int n, m;
    static int[] pick = new int[8];
    static bool[] used = new bool[9];
    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 num = 1; num <= n; num++) {
        if (used[num]) continue;
        used[num] = true;
        pick[depth] = num;
        Dfs(depth + 1);
        used[num] = false;
      }
    }

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

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

C++

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

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

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

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

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

  cin >> n >> m;

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

  return 0;
}