[ps]cpp_dfs_순열,조합,중복순열,중복조합

23 Apr 2024

4.17(수) 시험 리뷰
PS> 시험을 보기전, DFS와 BFS의 중요도를 깨달았지만, 어떻게 순열 및 조합을 구현하는지에 대해 큰 어려움이 있었다. 
    Idea는 확인했지만 Next_permutaion에 의존했달까..
    문제는 Next_permutaion의 사용법을 까먹었던걸 다시 알기까지 너무 오랜시간(1시간 30분..)이 걸렸고,
    Pro 문제를 핸들링할때, DFS로 기본적인 순열을 못 구현한다는 현실이 괴로웠다.
    next_permutaion (순열) 또는 pre_permutaion (조합)으로 문제를 풀어도된다고 하더라도, DFS 로 구현까지 학습해두자.
    ( 중복 조합, 중복 순열 문제가 나온다면 DFS로 풀어야하니..!!)

dfs는 길찾기에서는 (완전탐색문제)는 그다음 index로 이동(그 다음 Index가 휘향찬란했음 앞으로가고 뒤로가고 위로가고등) 하고, 조건에 따라 이동할 수 있으면 이동하는 느낌이었다.

하지만, 순열 조합을 dfs로 구현할때는 다음 index가 그 다음 수 일뿐이다. (그렇다면, 조합, 순열, 중복조,중복순은 DFS를 활용한 다채로운 구현! 의 문제가 될 것이다.) (하지만 순열의 경우에는 증가하는 index가 없다. 왜냐하면 뒤로 돌아가서 값들을 확인해야하기 때문)

ref : https://charles098.tistory.com/9

일단 중복을 걸러내기 위해서는 selected를 쓴다. 이건 graph or map에서의 visited 백터와 같은 역할을 한다. 즉 조합, 순열의 구현은 selected를 쓴다.

그럼 조합과 순열의 차이는 무엇일까?

조합은 뒤로 돌아갈 수 없다.
순열은 뒤로 돌아갈 수 있다.

이게 무슨소린가 싶겠지만, 이게다다

5C3 vs 5P3의 차이는 이렇다. (ex, map={1,2,3,4,5} )

5C3 -> 1,2,3 | 1,2,4 | 1,2,5 | 1,3,4 | 1,3,5 | 1,4,5 | 2,3,4 | 2,3,5 | 2,4,5 | 3,4,5 |

5P3 -> 1,2,3 | 1,3,2 | 2,1,3 | 2,3,1 | 3,1,2 | 3,2,1 | 
       
       1,2,4 | ...

       1,2,5 | ...

       1,3,4 | ...

       1,3,4 | ...

       1,4,5 | ...

       2,3,4 | ...

       2,3,5 | ...

       2,4,5 | ...

       3,4,5 | ...

패턴이 보이는가? 조합처럼 뽑아놓고, 순서를 생각하며 돌린다. 즉, 뒤로 돌아갈 수 있다는 것은 순열은 순서를 보면서 돈다는 것이다.

구현레벨에서 더 나아가서 생각하면 이렇다, 조합의 경우는 idx 가 dfs 파라미터에 들어가 있어서, 이전에 접근했던 값 이후부터만 for문이 돌도록 수행한다.

즉, 진행방향이 한쪾이다. 하지만, 순열의 경우 idx dfs 파라미터가 없어서 처음부터 확인을 하는 느낌이다.

굳이 비교를 하자면, 순열이 전체탐색의 concept과 동일하다. (전체를 다 돌면서 확인하니!)

그리고 중복과 일반의 차이는 “본인의 Index”를 포함하는가의 차이이다. 555 554 553 이건 즉, 5다음에 5가 들어갈 수 있다는말과 동일하니 본인의 Index를 포함하게 하고 싶다면, selected를 없애면 된다.**

그렇다면 구현 level로 생각해보자

조합이란?

순서를 고려한 뽑기이다. (중복이 없다) 즉 공을 뽑을 때, 화살표가 뒤로 돌아갈 수 있다. 중복이 없으니, selected로 중복되면 더이상 뽑지 말도록 해야한다.

예) GRAPH[5] = 1,2,3,4,5
5C3
1,2,3,
1,2,4
1,2,5
1,3,4
...

CODE

#include <iostream>
#include <vector>

using namespace std;

//N=5
int map[5] = {1,2,3,4,5}
int N,M;  // nCm


void dfs(int selected[],int idx, int cnt){
  if (cnt == M){
      for(int i=0; i<N; i++){
        if(selected[i]==1){
            print(map[i]);
        }
      }
  }
  else{
    for(int i=idx; i<N; i++){
      if (selected[i]==1) continue;
      selected[i] = 1; //중복조합의 경우 제거
      v.push_back(map[i]) // 중복조합의 경우 추가 
      dfs(selected, i,cnt+1); //조합
      dfs(selected, i,cnt+1,v); //중복조합
      v.pop_back() // 중복조합의 경우 추가 
      selected[i] = 0; //중복조합의 경우 제거
    }
  }
}


int main(){
  cin >> N >> M;
  int selected[5] = {0,}
  dfs(selected,0,0);
}



    

순열이란?

순서를 고려한 뽑기이다. (중복이 없다) 즉 공을 뽑을 때, 화살표가 뒤로 돌아갈 수 있다. 또한 공을 뽑은 뒤에는, 돌리기때문에 index의 증가를 차례대로 할필요가 없다. (하지만, 해야한다. 순서대로의 출력을 위해서)

예) GRAPH[5] = 1,2,3,4,5
5P5
1,2,3,4,5
1,2,3,5,4
1,2,4,3,5
1,2,4,5,3
...

CODE

#include <iostream>
#include <vector>

using namespace std;

//N=5
int map[5] = {1,2,3,4,5}
int N,M;  // nPm

void dfs(int selected,int cnt, vector<int> v){
    if(cnt==N){
      print(v);


    }
    else{
      for(int i =0; i<N; i++){
        if(selected[i]==1) continue;
        selected[i] = 1; //중복순열의 경우 제거
        v.push_back(map[i]);
        dfs(selected,cnt+1,v)
        v.pop_back(); 
        selected[i] = 0; //중복순열의 경우 제거
      }

    }
}


int main(){
  cin >> N >> M;
  int selected[5] = {0,};
  int
  dfs(selected,0);
}