일단 이 문제의 경우는 플로이드를 활용해서 각각의 노드별로 도달할 수 있는 길이를 최단경로로 갱신해놓고,
그렇게 갱신해놓은 최단경로 배열을 통해서 그 값들을 탐색해서 가장 적게 모든 별들을 탐색할 수 있는 경우에서의 총 탐색거리를 출력하면 되는 문제였는데,
이때에 모든 경우들을 탐색하면서 가장 적은 경우를 찾아내는 방법에는 두가지가 있었다.
첫번째로는 오랜만에 접하게된 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
일단 이 블로그를 통해서 관련 내용을 참고하면 좋을것 같다.
'알고리즘 > BOJ' 카테고리의 다른 글
boj 1238 번 문제를 통해 보는 다익스트라와 왕복 거리. (0) | 2023.07.26 |
---|---|
플로이드, 다익스트라, 벨만포드의 사용가능 상황 비교. (간략함) (0) | 2023.07.23 |
boj 11404번 문제를 풀며 접하게 된 fill 함수에 대하여. (0) | 2023.07.16 |
플로이드 알고리즘을 활용한 풀이에서 거리를 무한대의 의미로 놓기 위해 사용하는 0x3f3f3f3f와 0x7fffffff에 대하여. (0) | 2023.07.16 |
boj 16486번 문제를 통해서 보는 c++에서의 소수점 몇번째 자리 자리수와 fixed와 precision(); (0) | 2023.07.14 |