[LeetCode] C++ 332. Reconstruct Itinerary

https://leetcode.com/problems/reconstruct-itinerary/description/

 

문제

 

문제 분석

- 티켓들을 정렬 후 그래프로 구성한 뒤에 DFS 탐색을 하면 됩니다.

- 현재 노드를 바로 결과에 추가하는 방식으로 하면 더 이상 갈 수 있는 경로가 없을 때, 올바른 경로가 구성되지 않게 됩니다.

ex) tickets = [["JFK", "NRT"], ["JFK", "KUL"], ["NRT", "JFK"]] 의 경우 정렬 후 KUL이 먼저 나오게 되는데 JFK -> KUL로 가면 더 이상 갈 수 있는 경로가 없게 됩니다. 둘 다 가능한 경로라면 KUL이 먼저 나와야하지만, 경로가 가능한 경우에만 해당하기 때문에 가능하지 않은 경로라면 사전 순이 의미가 없게 됩니다.

- 따라서 경로를 끝까지 탐색한 후에 결과에 하나씩 추가하고 결과를 뒤집어 출력하는 방법이 안전합니다.

 

풀이

class Solution {
private:
    map<string, vector<string>> graph;
    vector<string> result;
    void dfs(string start){
        while (!graph[start].empty()) {
            string next = graph[start].front();
            graph[start].erase(graph[start].begin());
            dfs(next);
        }
        result.push_back(start);
    }

public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        std::sort(tickets.begin(), tickets.end());

        for (const auto& ticket: tickets){
            graph[ticket[0]].push_back(ticket[1]);
        }

        dfs("JFK");

        reverse(result.begin(), result.end());
        return result;
    }
};