BOJ-백준 15654번 N과 M(3) C++

BOJ-백준 15654번 N과 M(3) C++ 문제 풀이 입니다.

링크 : https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

 

 

 

✅ C++ 정답 코드 입니다. 더보기 클릭!

#include <iostream>
#include <vector>
#define MAX 8
using namespace std;

int n,m;
int arr[MAX];

//순열인데 중복해서 뽑아도 됨

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

int main() {
  cin >> n>>m;
  dfs(0);
}

 

 

 

📌 해설

중복이 있는 순열을 구하는 문제입니다. 백트래킹으로 해결하였습니다. 중복 가능하기 때문에 visited를 검사할 필요가 없었고 depth를 m까지만 dfs수행하면 순열을 구할 수 있습니다. 

 

#include <iostream>
#include <vector>
#define MAX 8
using namespace std;

int n,m;
int arr[MAX];

1. 필요한 변수와 헤더를 추가합니다. 

visited는 필요 없기 때문에 arr만 선언하여 중복이 있는 순열을 담습니다. 

 

int main() {
  cin >> n>>m;
  dfs(0);
}

2. n과 m 을 입력받고 dfs를 호출합니다. 

 

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

3. 백트래킹을 수행할 dfs 입니다. 

dfs는 depth 0부터 순차적으로 수행되면서 arr을 갱신합니다. 

즉, depth가 m이 되면 arr에 저장된 순열을 출력하고 dfs를 종료합니다. 

3-1. 1부터 n까지 숫자를 선택하기 위한 for문을 작성합니다. 

3-2. 현재 탐색중인 depth에서 숫자 i를 선택하여 arr을 갱신합니다. 이때, 방문여부는 체크하지 않기 때문에 이전 depth에서 이미 선택한 숫자도 arr에 넣을 수 있습니다. 

3-3. arr을 갱신하면 다음 depth를 수행하기 위한 dfs를 호출합니다. 

3-4. m 까지 depth를 통해 숫자를 선택하면 arr을 출력하고 dfs를 종료합니다. 

 

 

 

 

::