[L3] 프로그래머스 여행경로 C++ DFS, 해시맵, 우선순위 큐

리뷰

프로그래머스

 

해시맵을 통해 각 공항을 저장해 주고, ICN으로 부터 출발해 모든 항공권을 사용하여 모든 도시를 방문하는 문제

예제의 경우 모두 맞았지만 테스트 케이스에서 반만 맞는 경우가 생겼다.

answer에 공항 이름을 추가하는 로직을 후위로 위치하니 AC를 맞게 되었다.

 

 

전역 변수

• dic : 각 공항에서 이동할 수 있는 공항 정보를 오름차순으로 정렬하는 해시맵
• answer : 공항에 방문한 순서를 저장할 문자열 벡터

 

함수

1. dfs

void dfs(string s)

 

깊이 우선 탐색을 통해 공항을 방문하며 정답에 기록할 함수

1. 매개변수 s를 공항의 이름으로 받는다. 초기 공항의 값은 ICN이다.
2. ICN의 딕셔너리 value가 빌 때까지 반복문을 수행한다. value는 문자열 오름차순 우선순위 큐이다.
3. 사전순으로 가장 앞서는 공항을 빼내고, 해당 공항을 dfs함수의 매개변수로 전달하여 재귀를 진행한다.
4. 모든 인접 공항에 대한 탐색이 종료되었다면 answer에 현재 공항 이름을 추가해 준다.

 

문제풀이

1. 티켓 정보를 받아와 첫번째 공항을 key로, 두번째 공항을 value에 push해준다.
2. ICN공항부터 dfs함수를 통해 방문 처리를 시작하고 answer벡터에 공항 이름을 채워준다.
3. 현재 answer벡터는 역순으로 값이 입력되어 있으므로 reverse처리를 해준다.
4. answer 벡터를 리턴해준다.

 

참고 사항

dfs함수가 실행되고 곧바로 answer벡터에 공항이름을 넣으면 그리디한 최적해가 나오지 않는다.

이는 예제에서는 확인하기가 어려워 틀리기 쉬운 문제인 것 같다.

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

unordered_map<string, priority_queue<string, vector<string>, greater<string>>> dic;
vector<string> answer;

void dfs(string s) {
    while (!dic[s].empty()) {
        string nxt = dic[s].top();
        dic[s].pop();
        dfs(nxt);
    }
    answer.push_back(s);
}

vector<string> solution(vector<vector<string>> tickets) {
    for(const auto& ticket : tickets) dic[ticket[0]].push(ticket[1]);
    
    dfs("ICN");
    
    reverse(answer.begin(), answer.end());
    return answer;
}