AlgorithmBOJ

백준 외원판순회2 10971

,

1. 백준외원판순회2 10971

2. 컴퓨팅 스킬

  • W[i][j]는 도시 i에서 도시 j로 가기 위한 비용이므로 모든 경우의 수 완전탐색을 수행합니다.
  • N까지의 값을 vector에 넣어서 next_permutation을 수행합니다. next_permutation을 수행하는이유는 예를 들어 N이 4라고 하였을 경우 0,1,2,3까지의 값들을 vector에 넣고 모든 경우의 수를 만들어서 w[0][0], w[0][1]…w[0][3], w[1][0],w[1][1]…w[1][3]까지의 경우를 수행합니다.

3. 컴퓨팅 사고

  • 잘못 접근하였던점 저 맵을 보는순간 비에프에스로 풀어도될 것같은데 라는생각을 하였습니다. 하지만, 전혀 다른 문제였으며 완전탐색을 통해 풀어야합니다.
  • n값과 w 이차원배열에 비용을 입력받는다.
  • w[i][i] = 0일 경우 비용이 없습니다.
  • 모든 각 노드간의 간선의 비용에 따른 최소비용을 찾습니다.
  • 마지막노드와 첫번째 노드를 연결시키는 부분이 가장 핵심문제입니다.
  • 직접 손으로 그래프를 그려보았습니다.
  • 시간복잡도 O(N*N!) N! = 10! = 3628800

마지막노드에서 첫번째노드를 연결시킬 방법의 조건을 잘 찾아야한다. 가는경우의수와 다시 돌아오는 경우의수를 체크합니다.

4. 풀이

4.1. next_permutation을 사용한 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//
//  06_백준_외원판순회2_10971.cpp
//  algorithm-level-up
//
//  Created by kgh on 30/11/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int w[11][11];
int n;
int main(void){
    
    
    vector<int> v;
    
    cin >> n;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> w[i][j];
        }
    }
    
    for(int i=0; i<n; i++){
        v.push_back(i);
    }
    int min=210000000;
    sort(v.begin(),v.end());
    do{
        int sum = 0;
        bool check = true;
        for(int i=0; i<n-1; i++){
                if(w[v[i]][v[i+1]] == 0){
                    check = false;
                }else{
                    sum = sum + w[v[i]][v[i+1]];
                }
        }
        if(check && w[v[n-1]][v[0]] != 0){
            sum = sum + w[v[n-1]][v[0]];
            if(min > sum){
               min = sum;
            }
            
        }

        
       
    }while(next_permutation(v.begin(),v.end()));
    cout << min << "\n";
    
    return 0;
}

Share