여행경로(Level3)

• 문제 링크: 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 여행경로

• 문제 이해

  1. 주어진 티켓을 모두 사용하여 여행할 수 있는 경로를 찾습니다.
  2. 출발지는 무조건 "ICN"이며, 모든 여행지는 3글자입니다.
  3. 한 번 사용한 티켓은 다시 사용하지 않습니다.
  4. 출발지가 같은 티켓이 있다면, 도착지의 알파벳 순서가 빠른 곳 부터 방문합니다.

• 알고리즘 구현

  1. 출발지가 같은 티켓의 도착지를 알파벳 순서로 방문해야하므로(4), 먼저 정렬
     알고리즘을 수행합니다.
  2. 출발지는 "ICN"이므로, path에 "ICN"을 넣어두고 시작합니다.(2)
  3. 주어진 티켓을 모두 사용한다면, 성공한 경우이므로, 탈출조건은 모든 티켓을
     사용했을 때로 정합니다. (1)
  4. 한 번 사용한 티켓은 다시 사용하지 않기 위해서, 사용 후 방문 체크를 합니다.(3)
  5. 만약 경로를 완성하지 못한다면, 실패한 경우이므로, 방문 설정을 리셋 후 다른
     경로를 탐색합니다.

• 알고리즘

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

using namespace std;

int n;
vector<vector<string>> tickets;
bool solve(vector<string> &path, int visited) {
    if (visited == ((1 << n) - 1)) return (true);

    string tmp = "ZZZ";
    for (int nextStart = 0; nextStart < n; ++nextStart) {
        if (visited & (1 << nextStart)) continue ;
        if (tickets[nextStart][0] != path.back()) continue;
        path.push_back(tickets[nextStart][1]);
        // 해당 경로로 들어가서 실패하는 경우가 생기면, segment fault가 생겨버림
        bool ok = solve(path, visited | (1 << nextStart));
        if (ok) return (true);
        // 현재 경로를 가지 않았던 것으로 생각하고 새로운 경로 선택
        path.pop_back();
    }
    return (false);
}

vector<string> solution(vector<vector<string>> _tickets) {
    n = _tickets.size();
    tickets = _tickets;
    sort(tickets.begin(), tickets.end());

    vector<string> path;
    // 출발점 미리 입력
    path.push_back("ICN");
    solve(path, 0);
    return (path);
}