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

• 출처: 프로그래머스 43164
• 분류: DFS/BFS · Lv.3

문제

항공권 목록 tickets가 주어진다. "ICN"에서 출발하여 모든 항공권을 사용하는 여행 경로를 반환한다. 가능한 경로가 여러 개이면 알파벳 순서가 앞서는 경로를 반환한다.

핵심

모든 간선(항공권)을 정확히 한 번씩 사용하는 경로를 찾는다. tickets를 정렬한 뒤 DFS 백트래킹으로 처음 완성된 경로가 정답이다.

풀이

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

bool dfs(const string& cur, vector<vector<string>>& tickets,
         vector<bool>& used, vector<string>& path) {
    if (path.size() == tickets.size() + 1) return true;

    for (int i = 0; i < (int)tickets.size(); i++) {
        if (used[i] || tickets[i][0] != cur) continue;

        used[i] = true;
        path.push_back(tickets[i][1]);

        if (dfs(tickets[i][1], tickets, used, path)) return true;

        path.pop_back();
        used[i] = false;
    }
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());
    vector<bool> used(tickets.size(), false);
    vector<string> path = {"ICN"};
    dfs("ICN", tickets, used, path);
    return path;
}

메모

• 왜 간선 visited인가
  • 일반 DFS 문제는 모든 노드를 방문한다. 이 문제는 모든 간선(항공권)을 사용해야 한다
  • 같은 출발-도착 쌍의 항공권이 여러 장 있을 수 있다 (멀티그래프). used[i]로 각 항공권의 사용 여부를 개별 추적한다
• 백트래킹 동작
  • tickets를 정렬하면 같은 출발지에서 알파벳 순으로 시도한다. 처음 완성된 경로가 곧 정답이다
  • 경로가 막히면(path.size() < tickets.size() + 1인데 더 이상 갈 곳이 없으면) pop_back + used[i] = false로 되돌린다
  • return true로 첫 완성 경로를 찾는 즉시 재귀를 전부 종료한다
• 오일러 경로
  • 이 문제는 오일러 경로(Eulerian path) 문제이기도 하다. Hierholzer 알고리즘으로 O(E log E)에 풀 수 있다
  • 자세한 설명은 Hierholzer 알고리즘 정리 참고

복잡도

풀이	시간	공간
DFS 백트래킹	O(N!) 최악	O(N)
Hierholzer	O(E log E)	O(E)