[C++] 프로그래머스 - 여행경로

🔐 프로그래머스 - 여행경로

https://school.programmers.co.kr/learn/courses/30/lessons/43164

🔑 풀이

항공권이 주어졌을 때, 공항 경로를 출력하게 하는 문제이다. 이 문제에서 주의해야 할 점은

다음과 같다.

• 주어진 항공권을 모두 사용해야 한다.

• 방문 가능한 경우는 여러 개일 수 있으며, 알파벳 순서가 앞서는 경로를 정답으로 한다.

• 항상 “ICN” 공항에서 시작한다.

우선 주어지는 항공권 배열로부터 공항끼리의 연결 여부를 어떻게 구현할 지 생각해야 한다.

여러 가지 방법이 있겠지만, 한 공항에 대해 여러 공항의 경로가 존재할 수 있으므로,

공항을 key로, 연결된 공항들의 리스트를 value로 하는 map으로 구현하기로 했다.

주어진 항공권 배열에서 출발지와 도착지 정보를 map에 넣어 주었다.

map<string, vector<string>> flight;

for (int i = 0; i < tickets.size(); ++i) {
    string dep = tickets[i][0];
    string arr = tickets[i][1];
    flight[dep].push_back(arr);
}

또한, 가능한 경로가 여러 개일 경우, 알파벳 순서가 앞서는 경우를 정답으로 한다고 했으므로,

map의 각 연결된 공항 배열에 대해 정렬을 해 주었다.

for (auto& x : flight) {
    sort(x.second.begin(), x.second.end());
}

DFS를 통해 문제를 해결할 수 있는데, 문제에서 주어진 항공권을 모두 사용해야 한다는 조건이

존재하기 때문에, 경로 배열의 길이 = 항공권의 수 + 1 가 되야 함을 알 수 있다.
(각 항공권은 하나의 출발지와 도착지를 연결하기 때문에, 경로 상에 방문하는 공항의 수는 항공권 + 1)

if (temp_path.size() == ticket_count + 1) {
    answer = temp_path;
    return true;
}

종합해보면, “ICN” 부터 시작하여, 연결된 공항들을 경로에 추가하고, 경로가 완성되지 않으면,

백트래킹을 하여, 다른 경로를 탐색하는 과정을 통해 결과 배열을 얻는다.

🧩 코드