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

코딩테스트 연습 - 여행 경로 문제 바로가기

문제

해결 방법

문제 조건에서 주어진 티켓을 모두 사용할 수 있다고 보장하였으므로
완전 탐색 중 깊이 우선 탐색(DFS)를 사용해 문제를 해결하고자 하였습니다.

탐색을 진행하기 전, 티켓을 중복해서 사용할 수 없으므로 이용한 공항을 기록하고자 하였습니다.
문자열을 key 값으로 한 해시 테이블을 사용하고자 하였으나 출발지가 같은 티켓이 존재하여
해시 테이블 보다는 모든 티켓에 번호를 매기고 각 티켓의 사용여부를 기록하고자 하였습니다.

마지막으로 문제의 조건에서
“만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.” 라는 조건을 충족하기 위해
get_route 함수 호출 전 tickets 배열을 정렬하여 티켓 자체가 알파벳 순서로 정렬되도록 하였습니다.

정렬한 뒤 탐색하면 get_route 함수가 정렬된 티켓을 순차적으로 확인하기 때문에
결과 또한 알파벳 순서로 저장할 수 있습니다.

정답 코드

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

using namespace std;
bool* visited;

bool get_route(vector<vector<string>>& tickets, string curr_airport,
                        vector<string>& answer) {
    answer.emplace_back(curr_airport);
    if(answer.size() == tickets.size() + 1) return true;
    
    for(int i = 0; i < tickets.size(); ++i) {
        if(false == visited[i] && tickets[i][0] == curr_airport) {
            visited[i] = true;
            bool ret = get_route(tickets, tickets[i][1], answer);
            if(ret) return true;
            visited[i] = false;
        }
    }
    answer.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());
    visited = new bool[tickets.size()];
    fill(visited, visited + tickets.size(), false);
    vector<string> answer;
    get_route(tickets, "ICN", answer);
    return answer;
}

참고

[ 프로그래머스 여행 경로 (Lv3) ] (C++), 얍문님 블로그