프로그래머스 : 여행경로 (C++, Lv.3, DFS)

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

코딩테스트 연습 - 여행경로

여행 티켓 이름을 먼저 정렬하고 난 뒤 여행 티켓을 통해 경로를 탐색하면 처음으로 나온 경로가 알파벳 순으로 가장 빠른 여행지의 경로가 된다는 것을 블로그에서 보고 그 성질을 이용해 풀었다.

 

 

소스코드

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

using namespace std;
vector<string> airport;
bool finish = false;

void dfs(vector<vector<string>> tickets, vector<int> &ch) {
    //모든 공항을 경유한 경우 쭉 리턴
    if(airport.size() == tickets.size()+1) {
        finish = true;
        return;
    }
    
    for(int i = 0; i< tickets.size() ; i++) {
        //이미 사용한 티켓이거나 출발지가 다른 경우 스킵
        if(ch[i] == 1) continue;
        if(airport.back() != tickets[i][0]) continue;
        ch[i] = 1;
        airport.push_back(tickets[i][1]);
        dfs(tickets, ch);
        
        //이전 분기에서 이미 정답을 찾은 경우 계속 리턴
        if(finish == true) return;
        
        //아닌 경우 방문 해제
        ch[i] = 0;
        airport.pop_back();
    }
    
}


vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    //방문 체크 배열 생성
    vector<int> ch(tickets.size(), 0);
    //알파벳 순으로 앞에 오는 경로가 먼저 나오게 하기 위해 정렬
    sort(tickets.begin(), tickets.end());
    airport.push_back("ICN");
    //dfs 수행
    dfs(tickets, ch);
    
    answer = airport;
    
    return answer;
}