BOJ-백준 15649번 N과 M(1) C++

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

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

15649번: N과 M (1)

 

 

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

 

#include <iostream>
#define MAX 9
using namespace std;

int n,m;
int arr[MAX]={0,};
bool visited[MAX]={0, };

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 ++){
    if(!visited[i]){
      visited[i] = true;
      arr[depth] = i;
      dfs(depth+1);
      visited[i] = false;
    }
  }
}

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

 

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX 9
using namespace std;

int N,M; 
vector<int>graph;
int main() {

  cin>>N>>M;
  //Graph 생성
  for(int i=1; i<=N; i++){
    graph.push_back(i);
  }
  //next permutation
  do{
    for(int i=0; i<M; i++){
      cout<<graph[i]<<" ";
    }
    cout << "\n";
    reverse(graph.begin() + M, graph.end());
  }while(next_permutation(graph.begin(), graph.end()));
  return 0;
}

 

📌 해설

DFS를 활용한 백트래킹 문제입니다. 

백트래킹이란 해를 찾아가는 탐색을 하는 도중 지금 탐색 중인 경로가 해가 되지 않을 것 같으면 더 탐색하지 않고 되돌아 가는(Backtracking) 기법 입니다. 불필요한 탐색 연산 횟수를 줄이므로 효율적이라 할 수 있습니다. 이렇게 불필요한 탐색을 중단하고 다음 경로로 가는 것을 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미에서 가지치기(Pruning)를 한다고 합니다. 

 백트래킹은 완전 탐색(가능한 모든 경로를 탐색) 기법에 기반하며 완전 탐색 기법 중 하나로 DFS를 사용합니다. DFS는 모든 가능한 해(경로)를 탐색하는 반면, 백트래킹은 불필요한 경로는 사전에 차단하여 탐색하지 않고 최대한 올바른 해를 탐색합니다. 

 

이 문제에서는 순열을 백트래킹을 통해 구할 수 있습니다. 

그리고 백트래킹이 아닌 algorithm 헤더에 있는 next_permutation 모듈로도 똑같이 해결 할 수 있습니다. 

위 더보기 란에서 백트래킹로 해결한 코드, next_permutation으로 해결한 코드 모두 첨부하였습니다.

 

👍 백트래킹 풀이 

#include <iostream>
#define MAX 9
using namespace std;

int n,m;
int arr[MAX];
bool visited[MAX];

1. 필요한 변수를 선언하고, 헤더를 추가합니다. 

1-1. arr은 정렬된 순열을 담는 배열입니다. 

1-2. visited는 백트래킹을 하며 이미 방문된 숫자인지 판별하는 bool 배열 입니다. 

 

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 ++){
    if(!visited[i]){
      visited[i] = true;
      arr[depth] = i;
      dfs(depth+1);
      visited[i] = false;
    }
  }
}

2. depth를 매개변수로 받아 dfs의 깊이를 알 수 있도록 합니다. 

3. 만약 dfs의 깊이 depth가 m과 같다면 여태 arr 배열에 담긴 순열을 출력하고 dfs를 종료합니다. 

4. 1부터 n까지의 숫자를 탐색하는 for문을 작성합니다. 탐색할 숫자는 i 입니다. 

    4-1. 만약 i가 아직 방문되지 않은 숫자라면(arr에 담기지 않은 숫자라면) 방문 체크를 합니다. 

    4-2. 방문 체크를 한 뒤, 현재 dfs 깊이에 기록된 arr을 갱신합니다. arr[depth]는 i로 갱신됩니다. 

    4-3. dfs를 현재 depth+1 하여 수행합니다. (arr[m] 갱신되면 dfs가 차례로 탈출)

    4-4. arr[m]지점에서 저장된 i 부터 차례로 visited[i] 를 false로 갱신시키며 dfs가 종료됩니다. (되돌아감)

    4-5. 차례로 되돌아온 i 부터 다시 for 문이 돌며 visited[i]가 false 인 노드 i를 탐색합니다. (새로운 arr 갱신되고 arr[m]이 갱신되면 출력하고 다시 dfs 차례로 탈출 반복)

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

5. main 에서는 depth를 0부터 시작하는 dfs를 호출합니다. 

 

 

 

 

👍 next_permutaion 풀이

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX 9
using namespace std;

int N,M; 
vector<int>graph;

1. 필요한 변수를 선언하고 헤더를 추가합니다. 

 

int main() {
  cin>>N>>M;
  //Graph 생성
  for(int i=1; i<=N; i++){
    graph.push_back(i);
  }
  //next permutation
  do{
    for(int i=0; i<M; i++){
      cout<<graph[i]<<" ";
    }
    cout << "\n";
    reverse(graph.begin() + M, graph.end());
  }while(next_permutation(graph.begin(), graph.end()));
  return 0;
}

2. N과 M을 입력받고 벡터 graph를 생성합니다.

3. next_permutation 1234의 순열을 생성할때, 1234 1243 1324 1342 ... 으로 생성합니다. 다음 순열을 구할 수 없을때 false를 리턴하여 do while문을 종료하게 됩니다. 구하고 싶은것은 nPn이 아닌 nPr이므로 graph를 적절히 조정하여 순열을 구할 수 있도록 합니다. 아래 표는 동작 과정의 일부에 대한 설명입니다. 

 

12^(34)	^ 앞부분까지 출력 합니다.( r 까지 출력 )
(12 43) -> 13(24)	1243의 12는 이미 위에서 출력 했으므로 생략해야 합니다. 1234중 34를 뒤집어 1243으로 만들지 않으면 이 다음 순열인 1243을 for문이 돌게 됩니다. 즉, 필요한 출력이 끝나고 다음 순열을 만들어 주기 위해 graph를 조정하는 과정이 필요합니다. => reverse(graph.begin() + M, graph.end());
13^(24)	^ 앞부분까지 출력 합니다.( r 까지 출력 )
(13 42) -> 14(23)	1342의 13는 이미 위에서 출력 했으므로 생략해야 합니다. 1324중 24를 뒤집어 1342으로 만들지 않으면 이 다음 순열인 1324을 for문이 돌게되어 13이 출력 됩니다. 즉, 필요한 출력이 끝나고 다음 순열을 만들어 주기 위해 graph를 조정하는 과정이 필요합니다. => reverse(graph.begin() + M, graph.end());

 

 

 

 

 

참고

https://cryptosalamander.tistory.com/54

https://thd0011.tistory.com/19

https://chanhuiseok.github.io/posts/algo-23/

 

 

 

::

 

백트래킹은 실제로 문제를 많이 안 풀어보면 절대 혼자 못 풀것 같은....