풀이전략
- 문제를 읽어보면, 모든 도시를 방문해야 하고,
한번 갔던 도시 갈수 없는 -> 중복이 없다.
-> 즉 순열을 생각해내야 한다.
1,2,3 의 경우
123 / 132 / 231 / 213 / 312 / 321 이 나오는 모든 경우의 수를 획득할 수 있고, 중복이 없기 때문이다.
근데 문제를 보면
-
2차원 벡터에서 [i][j] 까지의 비용이고, 이를 사용하는 것이다.
-
어떻게 접근할까? 생각해보면
1,2,3 의 경우 , 결국에는 첫번째값으로 복귀해야 한다.
123 / 132 / 231 / 213 / 312 / 321 -
123 의 경우 1->2->3->1 이런식으로 진행하면 됨.
-
132 의 경우 1->3->2->1 이런식으로 진행하면 됨.
시간복잡도
: 도시전체의 수는 n < 10이기 때문에 10! 은 대충 4800000이므로
모든 경우의 수 진행해도 된다.
풀이
- 순열이기 때문에 벡터로 해당 n까지의 번호를 만든다.
- 이차원벡터에다가 위에서 만든 벡터값을 원소로 넣어가면서 진행하자.
🔥🔥🔥