[프로그래머스/c++] 여행경로

실패 코드

방법

티켓의 [a, b] 중 b를 기준으로 알파벳 순서가 앞서도록 정렬 후, 그 중에서 맨 앞의 ICN을 선택한 후 dfs 함수로 재귀를 통해 경로를 구하도록 하였다.

 

🤨 그 결과 다음과 같이 테스트 1, 2를 통과하지 못했다...

 

---

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> answer;
vector<vector<string>> t;
vector<int> ch(10000, 0);

bool cmp(vector<string> a, vector<string> b){
    return a[1]<b[1];
}

void dfs(int idx, string airport){
    if(answer.size()==t.size()+1){
        return;
    } else if(answer.size()<t.size()+1 && idx>=t.size()){
        idx=0;
    }
    if(t[idx][0]==airport && ch[idx]==0){
        answer.push_back(t[idx][0]);
        if(answer.size()==t.size()){
            answer.push_back(t[idx][1]);
        }
        ch[idx]=1;
        dfs(idx+1, t[idx][1]);
    } else{
        dfs(idx+1, airport);
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end(), cmp);
    int start_idx;
    
    for(int i=0; i<tickets.size(); i++){
        if(tickets[i][0]=="ICN"){
            start_idx=i;
            break;
        }
    }
    t=tickets;
    answer.push_back(tickets[start_idx][0]);
    ch[start_idx]=1;
    
    dfs(0, tickets[start_idx][1]);
    
    return answer;
}

 

---

실패 이유

가능한 경로가 2개 이상일 경우 알파벳 순서가 먼저인 경로를 return 하는게 맞지만, 무조건 알파벳 순서가 앞서는 곳을 향하도록 여행 경로를 구성하면 문제의 답을 올바르게 구할 수 없다!

 

위의 코드에서는 sort 정렬을 통해 알파벳 순서가 앞서는 ICN을 고르도록 되어 있는데,

[ICN, AAA]를 선택한 경우 가능한 경로가 없고, [ICN, BBB]를 선택한 경우 가능한 경로가 있다고 하면, 위의 코드대로라면 정답을 찾을 수 없는 것이다!

 

---

코드 변경 방법

• 그래서 더 이상 방문할 수 있는 도시가 없을 때 주어진 항공권을 모두 사용하지 못했다면, 다른 경로를 탐색하도록 해주어야 한다.

 

 

---

아래 링크에 이유가 잘 나와있다👇

https://school.programmers.co.kr/learn/courses/14743/lessons/118891

프로그래머스

 

---

성공 코드

• dfs 함수에 티켓을 모두 사용하였는지 확인하는 코드를 추가하였다.
• 티켓을 다 사용하지 못한 경우에는 answer에서 공항을 하나 꺼내고 조건을 만족하는 다른 공항을 골라 넣을 수 있도록 하였다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> answer;
bool visited[100000001];
bool check = false;

void dfs(string airport, vector<vector<string>> tickets, int count){
    if(count==tickets.size()){
        check=true;
    }
    answer.push_back(airport);
    
    for(int i=0; i<tickets.size(); i++){
        if(!visited[i] && tickets[i][0] == airport){
            visited[i]=true;
            dfs(tickets[i][1], tickets, count+1);
            
            if(!check){
                answer.pop_back();
                visited[i]=false;
            }
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());
    dfs("ICN", tickets, 0);
    
    return answer;
}

 

 

참고

https://ljhyunstory.tistory.com/107

코딩테스트 -- 여행경로 - (프로그래머스 / C++)