프로그래머스 - 여행경로 - Level 3

문제

풀이전략

1. 티켓은 한번만 사용하고, 주어진 티켓은 모두 사용해야한다. 따라서 DFS로 모든 경우를 다 찾고 그중 최소값을 찾는 문제이다.
2. ch배열을 통해 티켓을 중복으로 사용하지 않도록 해야한다.
3. 만약 가능한 경로가 2개일 경우에는 알파벳 순서가 앞서는 경로를 return해야한다. 따라서 경로가 다 완성이 되었을 때, 이전에 완성되었던 경로들과 비교하여 알파벳 순서가 우선인 것만 남기면 된다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
// 알파벳 순서 우선임을 찾기위한 함수
bool mySort(string& a, string& b){
    if(a[0] == b[0] && a[1]==b[1]) return a[2]<b[2];
    if(a[0] == b[0]) return a[1] < b[1];
    return a[0] < b[0];
}

// 중복을 막기위한 ch배열
bool ch[10001];
vector<string> answer;    
void DFS(vector<vector<string>> ticket, string curr, vector<string> ret){
    // 경로가 완성이 되면 알파벳순으로 크기비교 하도록 한다.
    if(ret.size() == ticket.size()+1){
        if(answer.empty()) answer = ret;
        else{
            for(int i=0; i<ret.size(); i++){
                if(answer[i] != ret[i]){
                    if(mySort(answer[i], ret[i])) break;
                    else answer = ret;
                }
            }
        }
        return;
    }
    // 갈수 있는 다음 도착지로 간다. 
    for(int i=0; i<ticket.size(); i++){
        if(!ch[i] && ticket[i][0] == curr){
            
            ch[i] = true;
            ret.push_back(ticket[i][1]);
            DFS(ticket, ticket[i][1], ret);
            ret.pop_back();
            ch[i] = false;
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> tmp;
    tmp.push_back("ICN");
    DFS(tickets, "ICN", tmp);
    
    return answer;
}

다른분 코드

// 나는 벡터를 파라미터로 주었찌만 이분은 string을 파라미터로 주어서 마지막에 짤랐다.
// 이 아이디어도 매우 중요한것 같다. 
#include <string>
#include <vector>

using namespace std;
int visited[1000000];
string ans_string = "a";

void dfs(vector<vector<string>> &tickets, string cur, string path, int depth) {
    if (depth == tickets.size()) {
        string p = path;
        // string으로 만들면 굳이 배열을 만들지 않더라도 이렇게 한번에 비교가 가능하다. 
        if (path < ans_string) {
            ans_string = path;
        }
        return;
    }
	// 나랑 아이디어는 같지만 string에 더해주는 더 편한 방법을 사용하였다. 
    for (int i = 0; i < tickets.size(); i++) {
        if (cur == tickets[i][0] && !visited[i]) {
            visited[i] = 1;
            dfs(tickets, tickets[i][1], path + tickets[i][1], depth+1);
            visited[i] = 0;
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    dfs(tickets, "ICN", "ICN", 0);
    // 티켓은 다 3개씩 짤리므로 이렇게 substr을 사용하여 문자열을 짤라주었다.
    for (int i = 0; i < ans_string.size(); i+=3) {
        answer.push_back(ans_string.substr(i, 3));
    }
    return answer;
}

소감

내 풀이랑 다른분이 푸신거랑 아이디어는 비슷하지만 저렇게 string으로만 푸는것이 훨씬 효율적이였다. 이런 아이디어도 꼭 생각할 수 있어야한다. 부스트캠프 준비를 위한 중요문제라고 생각하자.