여행경로 (프로그래머스)

주어진 조건으로 깊이 우선 탐색을 응용하는 문제였다. 

 

여기서 공항권은 a에서 b로 가는 것으로 그래프의 간선이라고 생각하면 된다. 이 공항권은 모두 사용해야 한다. 즉 그래프에 존재하는 모든 간선들을 지나가야 한다는 뜻이다. (마치 한 붓 그리기와 같다)

 

다음은 예제 2를 그래프로 표현한 것이다. 항상 인천공항에서 출발한다는 사실을 유의하자. 또한 경로가 위 그림처럼 여러개인 경우가 있을 수 있다.

ICN -> ATL -> SFO -> ATL -> ICN -> SFO

ICN -> ATL -> ICN -> SFO -> ATL -> SFO

ICN -> SFO -> ATL -> ICN -> ATL -> SFO 

다음과 같이 경로가 여러 개인 경우 알파뱃 순서가 앞서는 경로가 먼저 나오도록 해야 한다. 모든 경로의 두 번째 공항은 SFO보다 ATL이 먼저와야 하고, 3번째 공항은 SFO보다 ICN이 먼저 오기 때문에 최종적인 경로는 다음과 같다.

ICN -> ATL -> ICN -> SFO -> ATL -> SFO

입력되는 항공권의 경로들을 미리 내림차순으로 정렬해주면, 따로 검사를 해줄 필요 없이 알파뱃 순으로 경로를 갈 수 있게 된다.

 

위의 예를 깊이 우선 탐색을 이용하면 다음 그림 왼쪽과 같이 스택에 공항 이름이 들어간다. top 원소부터 꺼내면서 경로를 찾고 갈수 있는 경로가 없는 경우 그 공항은 스택에서 pop한다. 이 과정을 스택이 빌때까지 반복한다. 스택이 비었다면 꺼낸 모든 공항 이름을 반대 순서로 나열하면 우리가 구하는 최종적인 경로가 된다.

 

코드는 다음과 같다.

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    // 알파뱃 순서에 따른 여행 경로를 위해 미리 내림차순 정렬을 해준다.
    sort(tickets.begin(), tickets.end(), greater<vector<string>>());
    // 공항권 정보를 담고 있을 컨테이너
    unordered_map<string, vector<string>> r;
    // 깊이 탐색을 위한 스택
    vector<string> s;
    // 첫 경로는 인천공항이므로 미리 스택에 담아 놓는다.
    s.push_back("ICN");
    // 공항권 정보를 넣는다.
    for(int i = 0; i < tickets.size(); ++i) r[tickets[i][0]].push_back(tickets[i][1]);
    // 스택이 빌때까지
    while(!s.empty())
    {
        // 깊이 탐색 과정에서의 현재 공항 위치
        string airport = s.back();
        // 만약 공항권이 없을경우 (갈수 있는 경로가 없는 경우)
        if(r[airport].size() == 0 ||
           r.find(airport) == r.end())
        {
            // 최종 경로를 담을 컨테이너에 공항이름을 넣는다.
            answer.push_back(airport);
            s.pop_back();
        }
        else
        {
            // 내림차순으로 정렬했으므로 가장 뒤에 있는 공항이름이 조건에 맞는 공항이다.
            s.push_back(r[airport].back());
            r[airport].pop_back();
        }
    }
    // 최종경로는 스택에서 꺼냈으므로 반대방향일 것이다.
    // 고로 최종 경로를 담은 컨테이너를 반대로 뒤집어준다.
    reverse(answer.begin(), answer.end());
    return answer;
}