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

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

풀이

문제를 보면 주어진 항공권을 모두 이용하여라고 언급되어 있었다.
즉, 모든 경로를 한번씩 방문해줘야 하는데 처음에 도전할 때는 제대로 보지도 않고 그냥 모든 공항을 방문하는 식으로 코드를 작성했다.

DFS를 사용했고, vector을 stack 대신에 사용했다.
그러기 위해서는 vector에 공항 이름을 넣을 때, 알파벳 순서 중에서 후순위에 있는 것들을 먼저 넣어야 해서 sort로 먼저 정렬을 진행했다.

sort(tickets.begin(), tickets.end(), greater< vector<string> >());
처음에는 위 코드가 어떻게 정렬해주는지 어려웠다. 그래서 직접 코드를 작성해서 출력해봤더니,
[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL, SFO]]가
[[SFO, ATL], [ICN, SFO], [ICN, ATL], [ATL, SFO], [ATL, ICN]]로 정렬되는 걸 볼 수 있었다.
greater<자료형>()으로 인해 vector들이 내림차순이 되는데 만약 [0]이 같은 string이라면 [1]에 있는 값들을 내림차순으로 정렬해준다.

그리고 dfs 방법으로 공항을 하나씩 방문했다.

※ 잠깐! C++ Sort algorithm에 대해 공부하기

• 배열을 정렬할 때
  sort(arr, arr+n);
• 벡터를 정렬할 때
  기본 : sort(v.begin(), v.end());
  사용자 정의 함수(compare) 사용 : sort(v.begin(), v.end(), compare);
  내림차순 : sort(v.begin(), v.end(), greater<자료형>());
  오름차순 : sort(v.begin(), v.end(), less<자료형>());
• 연산자 오버로딩을 이용

중요 포인트

• unordered_map 사용
• 정렬을 통해 알파벳 순서를 지켜 방문하도록 해주는 것
• DFS 진행할 때 공항 이름 삽입, 삭제 잘하기

코드

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

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    unordered_map<string, vector<string> > m;
    
    sort(tickets.begin(), tickets.end(), greater< vector<string> >());
    
    for(int i = 0 ; i < tickets.size() ; i++){
        m[tickets[i][0]].push_back(tickets[i][1]);
    }
    
    vector<string> s = vector<string> {"ICN"}; // 벡터가 stack의 역할을 해준다.
    
    while(!s.empty()){
        string airport = s.back();
        if(m.find(airport) == m.end() || m[airport].size() == 0){
            // 갈수 있는 곳이 없거나 다 방문했다면
            answer.push_back(airport);
            s.pop_back();
        }else{
            s.push_back(m[airport].back());
            m[airport].pop_back();
        }
    }
    reverse(answer.begin(), answer.end());
    return answer;
}