프로그래머스_여행경로

https://programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로 | 프로그래머스

문제 자체는 dfs로 경로를 탐색하며 전개하면 되는데, 

알파벳 정렬 순으로 진행되어야 하기에 정렬이 필요하다.

그런데, 문제 조건에서 애매한 부분이 있는데 ["ICN", "BOO"], ["ICN", "BOO"] 와 같이 동일한 티켓이 두번 주어졌을 경우에 어떻게 처리해야 하는가 이다.

 

예제 테스트 케이스에서는 동일 티켓을 제외하고 처리하는게 맞다고 처리되는데

실제 채점에서는 동일 티켓도 고려하여 처리해야 정답이 처리가 된다...;;

황당하지만 밑의 첫 번째 코드는 테스트 케이스용, 두 번째는 채점용 코드이다.

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

vector<bool> check; // 체크용
vector<string> path; // 경로
vector<string> ans;
void print(vector<string> vs){
    cout<<vs[0]<<" "<<vs[1]<<"\n";
}

// 목적지 비교 정렬
bool compare(vector<string> v1, vector<string> v2){
    return v1[1] > v2[1];
}

void dfs(vector<vector<string>> t, string now, int cnt){
    // 경로 도달시 종료
    if(cnt == t.size()){
        ans = path; // 정답 이식
        return;
    }
    
    // 그 외 갈 수 있는 경로 탐색
    for(int i=0;i<t.size();i++){
        // 갈 수 있으면
        if(check[i]==false && t[i][0]==now){
            check[i]=true; // 탐색
            path.push_back(t[i][1]);
            dfs(t, t[i][1], cnt+1);
            check[i]=false; // 탈출
            path.pop_back();
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    sort(tickets.begin(), tickets.end(), compare); // 목적지별 정렬
    tickets.erase(unique(tickets.begin(), tickets.end()),tickets.end());
    check.assign(tickets.size(),false); // 체크
    
    path.push_back("ICN");
    dfs(tickets, "ICN", 0); 
    
    answer = ans;
    return answer;
}

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

vector<bool> check; // 체크용
vector<string> path; // 경로
vector<string> ans;
void print(vector<string> vs){
    cout<<vs[0]<<" "<<vs[1]<<"\n";
}

// 목적지 비교 정렬
bool compare(vector<string> v1, vector<string> v2){
    if(v1[0] == v2[0])
        return v1[1] > v2[1];
    return v1[0] < v2[0];
}

void dfs(vector<vector<string>> t, string now, int cnt){
    // 경로 도달시 종료
    if(cnt == t.size()){
        ans = path; // 정답 이식
        return;
    }
    
    // 그 외 갈 수 있는 경로 탐색
    for(int i=0;i<t.size();i++){
        // 갈 수 있으면
        if(check[i]==false && t[i][0]==now){
            check[i]=true; // 탐색
            path.push_back(t[i][1]);
            dfs(t, t[i][1], cnt+1);
            check[i]=false; // 탈출
            path.pop_back();
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    sort(tickets.begin(), tickets.end(), compare); // 목적지별 정렬
    //tickets.erase(unique(tickets.begin(), tickets.end()),tickets.end());
    check.assign(tickets.size(),false); // 체크
    
    path.push_back("ICN");
    dfs(tickets, "ICN", 0); 
    
    answer = ans;
    return answer;
}