백준 10971 - 외판원 순회 2 - dfs 를 이용한 순열 구현

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

10819 차이를 최대로 문제에서 순열을 dfs로 구현하는 것에서 아이디어를 따와 풀었다.

거기보다 이 문제에서 조금 더 주의해야 할 점은, 마을마다 방문한 노드는 다시 방문하면 안되는 것은 기본이고,

edge가 0인 경우에는 갈수 없다는 조건까지 검사해보아야 한다.

 

일단 이건 60%까지 갔다가 틀린 코드.

#include <iostream>
#include <vector>
using namespace std;
 
int map[11][11];
bool isvisited[11];
int N;
int result= 99999999;
vector<int> v;
 
void dfs(int travelcnt, int currentnode){
    if(travelcnt==N){
        int tmp=0;
        for(int i=0; i<N-1; i++){
            tmp+=map[v[i]][v[i+1]];
        }
        tmp +=map[v[N-1]][v[0]];
        result = min(result,tmp);
//        cout<<"result is "<<result<<"\n";
        return;
    }
    else{
 
        for(int j=0; j<N; j++){
            if(map[currentnode][j]==0)
                continue;
            else if(!isvisited[j]){
//                cout<<currentnode<<" -> "<<j<<"\n";
                isvisited[j]=true;
                v.push_back(j);
                dfs(travelcnt+1,j);
                isvisited[j]=false;
                v.pop_back();
            }
        }
    }
}
 
int main(void){
 
    cin>>N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin>>map[i][j];
        }
    }
    dfs(0,0);
    cout<<result;
}

왜 틀렸을까에 대한 의-심과 든생각들

1. result가 99999999를 넣은 것이 잘못? 더 큰 숫자로 넣었어야했나.

2. 질문게시판을 봤는데, 마지막에 예를들어 1 2 3 4-->1 에서 4-->1 로 돌아오는 길을 내가 체크를 안해서 틀렸을 가능성이 매우 높다고 판단했다.

 

2.를 고쳐서 다시 돌려봤더니 AC를 받았다.

#include <iostream>
#include <vector>
using namespace std;
 
int map[11][11];
bool isvisited[11];
int N;
int result= 99999999;
vector<int> v;
 
void dfs(int travelcnt, int currentnode){
    if(travelcnt==N){
        int tmp=0;
        for(int i=0; i<N-1; i++){
            tmp+=map[v[i]][v[i+1]];
        }
        if(map[v[N-1]][v[0]]==0)
            return;
        else {
            tmp += map[v[N - 1]][v[0]];
            result = min(result, tmp);
//        cout<<"result is "<<result<<"\n";
            return;
        }
    }
    else{
 
        for(int j=0; j<N; j++){
            if(map[currentnode][j]==0)
                continue;
            else if(!isvisited[j]){
//                cout<<currentnode<<" -> "<<j<<"\n";
                isvisited[j]=true;
                v.push_back(j);
                dfs(travelcnt+1,j);
                isvisited[j]=false;
                v.pop_back();
            }
        }
    }
}
 
int main(void){
 
    cin>>N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin>>map[i][j];
        }
    }
    dfs(0,0);
    cout<<result;
}

여담으로, 다른 사람들 채점현황 보니까 한번에 맞춘 사람은 없더라고,,

은근 한방에 2. 조건을 생각하기 사람들도 쉽지는 않았나보다.