JArchive 프로그래밍 일기

문제

외판원 순회2 백준 10971번

리뷰

N개의 도시가 있다. 어떤 도시에서 시작해서 모든 도시를 방문하고 다시 시작 도시로 돌아오는 최소 비용을 구하는 문제.

완전탐색으로 풀었다.

N개 도시를 모두 시작점 삼아서 탐색해봐야 한다.

for문 하나면 되는데, 이중 for문으로 해서 틀렸었다...

탐색 함수의 시그니처는 아래와 같다.

void search(int visit_city, int cnt, int cost);
// visit_city는 현재 도시 번호
// cnt는 그동안 방문 도시 개수
// cost는 이동하면서 누적한 비용

cnt가 N개가 되는 순간, 현재 지점에서 '시작점' 으로 갈 수 있는지 확인하고, 이동 후 최소비용을 갱신한다.

search 함수 내부에 재귀호출이 있는 for문이 있다.

i와 j간에 경로가 없는 경우 m 배열 값이 0이니까 continue 처리한다.

이미 방문한 도시도 재방문하면 안되니까 continue 처리한다.

void search(int visit_city, int cnt, int cost){

    if(cnt == N ){ // 모든 도시 방문했고, 목적지 도착시 종료   
        if(m[visit_city][start_city] > 0){ // 시작점으로 돌아옴. 
            mcost = min(cost + m[visit_city][start_city], mcost);
        }
        return; 
    }

    for(int a = 0; a < N; a++){ 

        if(m[visit_city][a] == 0) continue; // 못가는 곳  
        if(visit_check[a] == true) continue; // 이미 방문한 도시 

        visit_check[a] = true; // 방문표시  
        search(a, cnt+1, cost + m[visit_city][a]); // 방문해본다  
        visit_check[a] = false; 
    }
}

코드1

#include <iostream>
#include <algorithm> 
using namespace std;

// 외판원순회2

int N;
int m[11][11];
int visit_check[11]; // 방문체크 
int mcost = 2e9;  // 최소비용 
int start_city; // 시작지점이자 목적지점

void search(int visit_city, int cnt, int cost){

    if(cnt == N ){ // 모든 도시 방문했고, 목적지 도착시 종료   
        if(m[visit_city][start_city] > 0){ // 시작점으로 돌아옴. 
            mcost = min(cost + m[visit_city][start_city], mcost);
        }
        return; 
    }

    for(int a = 0; a < N; a++){

        if(m[visit_city][a] == 0) continue; // 못가는 곳  
        if(visit_check[a] == true) continue; // 이미 방문한 도시 

        visit_check[a] = true; // 방문표시  
        search(a, cnt+1, cost + m[visit_city][a]); // 방문해본다  
        visit_check[a] = false; 
    }
}


int main(void){

    cin >> N; // 도시 개수 

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> m[i][j];
        }    
    } // 입력받기 끝. 

    for(int i = 0; i < N; i++){

        start_city = i; // 시작 도시 번호 
        visit_check[i] = true; // 시작 도시 방문했으니까 cnt 1 로 시작 
        search(i, 1, 0); 
        visit_check[i] = false;
    }

    cout << mcost;

    return 0;
} 

코드2

next_permutation() 써서 풀 수 있다. 왜냐하면, 어떤 순서대로 도시를 방문해야 하는가 의 문제이기 때문에.

순열을 리턴해주는 함수로 해결가능하다.

도시 번호 수열을 만들기 위해 A [ ] 배열을 만든다. 1 2 3 ... N 의 숫자가 들어간다.

마지막 N번 도시에서 1번 도시로 (시작점으로) 오는 경로가 있는 경우 비용을 합산한다.

next_permu() 함수가 만들어주는 수열 대로 방문한다.

경로가 없으면 모든 도시를 방문할 수 없기 때문에 all_visit 플래그를 활용한다.

모든 경로를 방문한 경우에만 최소비용을 갱신한다.

#include <iostream>
#include <algorithm> 
using namespace std;

// 외판원 순회2 

int N;
int M[11][11];
int A[11]; // 도시 번호 


int main(void){

     freopen("input.txt", "rt", stdin);

    cin >> N;

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cin >> M[i][j];
        }
    } // 도시 간의 경로 입력받기 끝. 


    for(int i = 1; i <= N; i++){ // 도시에 번호 붙이기 (1부터 N까지) 
        A[i] = i;
    }

    int mincost = 2e9;

    do{
        int cost = 0;
        bool all_visit = true;
        int i = 1;

        for(i = 1; i <= N-1; i++){

            if(M[A[i]][A[i+1]] > 0){
                cost += M[A[i]][A[i+1]];
            }else{
                all_visit = false; // 경로가 없어서 실패.
                break;
            }
        }

        // 마지막 N번 도시에서 1번 도시로 (시작점으로) 오는 경로가 있는 경우 비용을 합산.
        if(M[A[N]][A[1]] > 0) cost += M[A[N]][A[1]];
        else all_visit = false; // 모든 도시 방문 실패.  

        if(all_visit){
            mincost = min(cost, mincost);
        }

    }while( next_permutation(A, A+N));

    cout << mincost;

    return 0;
}