[프로그래머스 Lv3] : 여행경로

문제 링크

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

코딩테스트 연습 - 여행경로

비행기 표가 주어졌을 때 모든 표를 사용해서 여행할 수 있는 경로를 리턴하는 문제.

 

풀이

 각각의 공항을 노드라고 생각했을 때 공항 i에서 j로 가는 표가 있으면 i와 j 사이에 간선이 존재한다고 생각할 수 있다.

ICN 공항을 시작 노드로 연결된 노드들로 이동해서 모든 노드를 방문할 때까지 이동한다.

모든 노드를 방문했을 때 그때까지의 방문 경로를 answer 벡터에 담아서 리턴한다.

 

하지만 문제 조건에 보면

만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.

라는 조건이 있다.

경로가 여러개일 경우 사전순으로 앞서는 경로를 리턴해야한다.

그래서 나는 모든 경로를 모아서, 정렬한 후 제일 앞에있는 경로를 리턴하는 방식을 선택했다.

모든 경우의수를 탐색하면서

1. 경로를 하나의 문자열로 합친다. 만약 ICN -> JFK -> HND 면 "ICNJFKHND" 이렇게

2. 경로를 모두 vector<string> all_route 벡터에 저장한다.

3. 벡터를 정렬한다.

4. 0번째 인덱스에 있는 문자열을 3글자씩 쪼개서 answer 벡터에 넣는다.

 

코드 작성

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 10000 + 5;
bool visited[MAX_N];
vector<string> all_route;
 
void dfs(int depth, string now, vector<vector<string>> tickets, string result){
    if(depth == tickets.size()){
        all_route.push_back(result);
        return;
    }
    for(int i = 0; i<tickets.size(); i++){
        if(!visited[i] && tickets[i][0] == now){
            visited[i] = true;
            dfs(depth + 1, tickets[i][1], tickets, result + tickets[i][1]);
            visited[i] = false;
        }
    }
}
void get_answer(string ans, vector<string> & answer){
    for(int i = 0; i<ans.length(); i+=3)
        answer.push_back(ans.substr(i,3));
}
vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    dfs(0, "ICN", tickets, "ICN");
    sort(all_route.begin(), all_route.end());
    get_answer(all_route[0], answer);
    return answer;
}

 

여기서 굳이 모든 경로를 벡터에 저장해지 않고 그때 그때 비교를 통해서 사전순으로 앞서는 경로로 갱신해주는 것도 하나의 방법인 듯하다.

<, > 연산자를 써서 문자열을 사전순을 기준으로 비교할 수 있다.