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

1번 테케 실패한 코드

(엉망징창)

직접 추가한 테스트 케이스 (모두 성공)

1) [["ICN", "JFK"], ["JFK", "IAD"], ["IAD", "JFK"], ["JFK", "HND"]]  & ["ICN", "JFK", "IAD", "JFK", "HND"]

2) [["ICN", "JFK"], ["JFK", "IDD"], ["IDD", "JFK"], ["JFK", "ICN"]] & ["ICN", "JFK", "IDD", "JFK", "ICN"]

3) [["ICN", "JFK"], ["JFK", "IAD"], ["IAD", "JFK"], ["JFK", "IAD"]] &  ["ICN", "JFK", "IAD", "JFK", "IAD"]

4) [["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]] & ["ICN", "BOO", "DOO", "BOO", "ICN", "COO", "DOO", "COO", "BOO"]

5) [["ICN", "AAA"], ["ICN", "AAA"], ["ICN", "AAA"], ["AAA", "ICN"], ["AAA", "ICN"]] & ["ICN", "AAA", "ICN", "AAA", "ICN", "AAA"]

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

vector<string> answer;
vector<int> done(10002); 
void nxt(int strIDX , int endIDX, string target, vector<vector<string>>& tic){
    bool finds= false;
    for(int i=strIDX;i<endIDX;i++){
        if(tic[i][0] == target && done[i] == 0){
            finds=true;
            answer.push_back(tic[i][1]);
            done[i] = 1;
            if(tic[i][1]>target){
                nxt(i+1,tic.size(),tic[i][1],tic);
            }else{
                nxt(0,i,tic[i][1],tic);
            }
        }
    }
    
    if(finds == false && answer.size() != tic.size()+1){
        answer.pop_back();
        if(strIDX == 0){
            done[endIDX] = 0;
        }else{
            done[strIDX-1] = 0;
        }
        return;
    }
}
vector<string> solution(vector<vector<string>> tickets) {
    
    sort(tickets.begin(),tickets.end());
    
    answer.push_back("ICN");
    nxt(0,tickets.size(),"ICN",tickets);
    
    return answer;
}

 

 

2번 성공한 코드 

 

** 18번째 줄 

-  루트가 끊기지 않은 경우에는 재귀타고 들어가며 전체 다 돌고, 다시 나올때 여기를 만나게 됨 
    ->그땐 이미 answer 크기랑 경로 개수 +1 이 같게 되므로 여기 코드 건너 뛰게 됨

 

도움이 된 테스트 케이스 (질문하기에서 찾음)

입력 : [["ICN", "COO"], ["ICN", "BOO"], ["COO", "ICN"], ["BOO", "DOO"]] -> 결과 :["ICN", "COO", "ICN", "BOO", "DOO"]

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

vector<string> answer;
vector<int> done(10002); 
void nxt(int preIDX, string target, vector<vector<string>>& tic){
    
    for(int i=0;i<tic.size();i++){ 
        if(tic[i][0] == target && done[i] == 0){//적절히 루트 타고 들어온경우
            answer.push_back(tic[i][1]);
            done[i] = 1;
            nxt(i,tic[i][1],tic);
        }
    }
    if(answer.size() != tic.size()+1){ //루트가 끊긴경우 위의 if문을 실행하지 못하고 여기가 실행됨
        answer.pop_back();
        done[preIDX] = 0;
        return;
    }
}
vector<string> solution(vector<vector<string>> tickets) {
    
    sort(tickets.begin(),tickets.end());
    answer.push_back("ICN");
    nxt(0,"ICN",tickets);

    return answer;
}