프로그래머스-여행경로

문제 링크

1. 문제 접근 과정🧐

1. 모든 간선을 한번만 방문해야 하므로 오일러 경로를 활용
2. 항공권의 from, to를 map과 multiset을 활용하여 저장
3. 스택으로 시작인 ICN을 넣고 빌 때까지 반복
4. 다음으로 방문할 공항이 없다면 answer에 넣고 pop
5. 방문할 공항이 있다면 사전 순을 위해 multiset의 처음을 스택에 추가하여 처음 요소는 방문 처리를 위해 multiset에서 제거
6. 반복문이 끝나면 스택은 LIFO이므로 answer을 뒤집으면 답이 됨

2. 시행착오🤯

• 처음에 사전 순으로 방문을 위해 우선순위큐로 구현하였다가 실패했다.
  • 해당 방법으로 하면 2가지 이상의 문제가 있다.
  1. 우선순위큐를 활용하면 경로대로 가는 것이 아니라 방문 순서를 제어해버린다.
  2. multiset의 요소를 지우는 방식이 잘못됐다. for문으로 방문 중에 지워버려 방문이 꼬일 수 있다.
• 오답 코드

#include <string> 
#include <vector> 
#include <map> 
#include <set>
#include <queue> 

using namespace std; 

vector<string> solution(vector<vector<string>> tickets) { 
    vector<string> answer; 
    map<string, multiset<string>> m; 
    for(int i = 0; i < tickets.size(); i++){ 
        string from = tickets[i][0], to = tickets[i][1]; 
        m[from].insert(to);
    }
    priority_queue<string, vector<string>, greater<string>> pq; 
    pq.push("ICN"); 
    while(!pq.empty()){ 
        string cur = pq.top(); 
        pq.pop(); 
        answer.push_back(cur); 
        for(string next : m[cur]){ 
            pq.push(next);
            m[cur].erase(next); 
        } 
    } 
    return answer; 
}

3. 개선한 코드😄

• 이 문제를 통해 오일러 경로라는 것을 알게 되어 활용하여 풀었다.
  • 오일러 경로란 모든 간선을 한번만 방문하여 경로를 찾는 것이다.
• 갈 수 없을 때까지 방문하고 갈 수 없으면 해당 공항을 answer에 추가하여 마지막에 뒤집으면 해결
  
• 정답 코드

#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>

using namespace std;

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    map<string, multiset<string>> m;
    for(int i = 0; i < tickets.size(); i++){
        string from = tickets[i][0], to = tickets[i][1];
        m[from].insert(to);
    }
    stack<string> s;
    s.push("ICN");
    while(!s.empty()){
        string cur = s.top();
        if(!m[cur].empty()){
            auto next = m[cur].begin();
            s.push(*next);
            m[cur].erase(next);
        }
        else{
            answer.push_back(cur);
            s.pop();
        }
    }
    reverse(answer.begin(), answer.end());
    return answer;
}

4. 회고💭

• 오일러 경로라는 개념을 처음 알게 되어 공부를 하였다.
• 이 문제가 오일러 경로인 이유는 모든 티켓을 정확히 한 번씩 사용해서 경로를 만들어야 하고 같은 공항을 여러 번 가더라도 간선은 한번만 사용해야 하기 때문이다.
• 만약 시작점과 끝점이 같아 순환이 되면 오일러 회로가 된다.