boj 17182번 문제를 통해 다시 접하게된 next_permutation(); 에 대하여.

일단 이 문제의 경우는 플로이드를 활용해서 각각의 노드별로 도달할 수 있는 길이를 최단경로로 갱신해놓고, 

그렇게 갱신해놓은 최단경로 배열을 통해서 그 값들을 탐색해서 가장 적게 모든 별들을 탐색할 수 있는 경우에서의 총 탐색거리를 출력하면 되는 문제였는데, 

이때에 모든 경우들을 탐색하면서 가장 적은 경우를 찾아내는 방법에는 두가지가 있었다. 

첫번째로는 오랜만에 접하게된 next_permutation을 이용해서, 이 문제의 경우 n의 범위가 10으로 매우 작다는걸 이용해서 

모든 가능한 경우들에 대한 연산을 수행해서 찾아내는 것이고, 

두번째 방법은 dfs를 이용한 백트래킹을 통해서 탐색해 들어가면서 가장 짧은 경로를 찾는 방법이었다. 

 

이 글에서는 첫번째로 제시한 next_permutation을 활용한 방법에 대해서 글을 작성해보겠다. 

일단 next_permuatation을 활용한 형태의 풀이들을 보면, 

do{

//연산수행

}while(next_permutation(comb.begin(),comb.end()));

형태의 코드를 볼 수 있게 되는데,

여기서 잘 알아야 하는건, 결국 next_permutation을 사용하면, 그 다음 순서로 변경이 (한번) 일어난다는 것이다. 

그걸 한번 일으키고, 그 다음에 do 내부에 있는 연산이 수행되고, 그리고 다시 while 내부에서 next_permutation이 (한번) 일어나고, 

하는 형태의 식으로 로직을 작성해서 next_permutation을 이용해서 모든 경우들을 탐색할 수 있게 만드는 것이다. 

그래서 먼저 기본적으로 next_permutation은 다음 순서로 바꾸어서(이때 순서는 사전식) 한번 변형 시켜준다는것을 기억하고, 

이 형태로 모든 경우들을 탐색하게 만들어 주는 방법은

 

do{

//수행할 연산

}while(next_permutation(컨테이너)); 

형태의 do while문의 구성을 통해서라는걸 알아야 한다. 

그래서 이번 문제의 경우는, st 위치를 제외하고 나머지 행성들의 번호를 vector에 담아서, 그 vector로 

next_permutation을 이용한 do while문을 돌려서 각각의 경우들에 해당하는 모든 탐색거리를 구해서, 그중에서 최소가 되는 값을 찾아서 기록을 갱신하면서 모든 연산을 마친뒤에 그 값을 출력하는 형태로 풀 수 있었던 것이다. 

 

이때에 일반적인 플로이드 알고리즘 부분은 제외하고, 

이 문제를 next_permutation을 활용한 모든 경우의 수를 체크하게 만들기 위해 필요한 코드들을 첨부해보면, 

 

// st를 제외한 부분들을 vector에 담아서 next_permutation에 활용할 수 있는 형태로 만듬
int n, st; cin >> n >> st;
  for(int i = 0; i < n; i++)
    if(i != st) comb.push_back(i);

/*do while문을 통해서 코드에 대한 실행을 한뒤에 next_permutation으로 얻어지는 다음 순서의 순열에 대해서
do 안에 있는 코드를 수행 할 수 있도록 세팅함. 
이 코드의 형태를 통해서 지속적으로 next_permutation을 통해서 다음 순서의 순열로 넘어가면서 
do 안에서 실행하는 형태의 코드를 모든 경우의 순열들에 대해서 시행함. 
*/ 
  do {
    int tmp = adj[st][comb[0]];
    for(int i = 1; i < n - 1; i++)
      tmp += adj[comb[i - 1]][comb[i]];
    ans = min(tmp, ans);
  } while(next_permutation(comb.begin(), comb.end()));

 

그리고  next_permutation에 대해서 검색해서 첨부해보면, 

 

딱 이러한 형태를 통해서 

예를들어 n이 3인 경우이고, 시작이 0인 경우에서 모든 경우의 수들을 next_permutaiton을 활용한 do while문의 형태를 통해서

0 1 2

0 2 1

1 0 2

1 2 0 

2 0 1

2 1 0 

의 경우들로 나타내어서 모두 계산 할 수 있다. 

 

오랜만에 만난 next_permutation을 이용한 모든 경우의 계산이었는데, 

next_permutation을 이용해서 다음 순서로 변경(한번)

do while문의 형태를 이용한 모든 경우로의 확장 

이라는 두가지로 나누어서 next_permutation을 활용한 모든 경우의 계산에 대해서 잘 기억해보도록 하자. 

 

 

+++++++++++

이 문제에 대한 백트래킹을 이용한 풀이를 다음에 추가하도록 하겠다

https://imnotabear.tistory.com/233

 

일단 이 블로그를 통해서 관련 내용을 참고하면 좋을것 같다. 

 

  Comments,     Trackbacks