Programmers / BFS, DFS / 여행 경로

< 문제링크 >

https://www.welcomekakao.com/learn/courses/30/lessons/43164?language=cpp

< 풀이 >

1. 가능한 경로가 두개 이상일 경우, 알파벳 순서가 앞서는 경로를 찾아야 된다. 그러므로 탐색 순서를 알파벳순으로 하면 해결되기 때문에, 초기 항공권 배열을 오름차순으로 정렬한다.

2. 알파벳순으로 탐색하므로, DFS를 수행해서 제일 먼저 모든 항공권을 사용한 경우가 정답이다.

3. 주의할 점은 틀린 경로라면 다시 돌아가서 rollback 작업을 수행할 것인데, 해답을 찾은 경우에도 재귀적으로 함수를 빠져나가므로 rollback 하지 않고 return 하도록 처리해야 한다.

< 코드 >

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

using namespace std;

vector<string> path;
bool flag = false;

// 항공권 배열을 오름차순으로 정렬하기 위한 함수
bool cmp(vector<string> a, vector<string> b)
{
    if (a[0] < b[0]) return true;
    else if (a[0] == b[0]) {
        return a[1] < b[1];
    }
    return false;
}

void find_path(vector<vector<string>> tickets, vector<bool> visited, string cur, int n)
{
    // 모든 항공권을 다 썼다면 정답
    if (n == tickets.size()) {
        // 정답을 찾았음을 표시
        flag = true;
        return;
    }
    for (int i = 0; i < tickets.size(); i++) {
        if (visited[i]) continue;
        if (tickets[i][0] != cur) continue;
        // 현재 도시에서 갈 수있는 곳 중 사용하지 않은 항공권을 사용
        visited[i] = true;
        path.push_back(tickets[i][1]);
        find_path(tickets, visited, tickets[i][1], n + 1);
        // 만약 정답을 찾았다면 경로를 rollback 하지 않고 return
        if (flag) return;
        // 경로를 못찾았다면 rollback
        visited[i] = false;
        path.pop_back();
    }
    return ;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<bool> visited(tickets.size(), false);
    sort(tickets.begin(), tickets.end(), cmp);
    path.push_back("ICN");
    find_path(tickets, visited, "ICN", 0);
    answer = path;
    return answer;
}

int main(void)
{
    vector<vector<string>> tickets = { {"ICN", "SFO"},{"ICN", "ATL"},{"SFO", "ATL"},{"ATL", "ICN"},{"ATL", "SFO"} };
    vector<string> answer = solution(tickets);
    for (auto i : answer) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}