프로그래머스 - 여행 경로

TC 1번을 제외하고는 쉽게 풀렸는데 1번이 너무~너무 안풀려서 많이 헤맨 문제이다.

 

참고한 코드

#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;
        if (path < ans_string) {
            ans_string = path;
        }
        return;
    }
 
    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);
    for (int i = 0; i < ans_string.size(); i+=3) {
        answer.push_back(ans_string.substr(i, 3));
    }
    return answer;
}
 

TC 1번은 경로가 같은 것이 2개 이상 있어서 알파벳 순으로 앞선 것을 고려해야 맞는다고 하는데, 단순히 tickets를 정렬해서 해결될 문제는 아닌 것 같다. 

 

가장 놀라웠던 부분은 visited[i] = 1; dfs호출; visited[i] = 0을 해줬다는 부분이다. 

visited 배열을 초기화 해줌으로써 모든 경우에 대한 path를 구할 수 있고 path를 string으로 관리하여 현재 답으로 채택된 string과 path를 비교하여 더 작은 것이 답이 되도록 해야한다. (즉, 도착지가 앞선 것이 아니라 애초에 경로 전체가 알파벳 순으로 앞서야 한다는 것이다. -> 이걸 몰랐던 것 같다.)

 

string을 이용하여 sorting하지 않고도 쉽게 알파벳 순으로 앞선 것을 골라낸 점이 인상적이어서 많이 배운 코드인 것 같다.

 

다음에 꼭 혼자 힘으로 다시 풀어봐야 겠다.