[pro] 프로그래머스 level3 43164 여행경로 (c++) - DFS

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/43164?language=cpp 

프로그래머스

 

[풀이]

이전에도 풀었던 문제라 해설은 생략. 사용하지 않은 티켓이고, 현재 위치가 티켓의 출발지점과 일치할 때 DFS를 새로 호출하면 된다.

 

c++은 split() 함수가 없어서 split() 함수를 stringstream을 이용해 구현해서 사용해야 했다. split() 함수는 꽤 유용하기 때문에 기억해두면 좋을 듯. 

 

[코드]

 

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

using namespace std;

vector<string> list;
bool visited[10000];
int n;

vector<string> split(string s, char del){
    vector<string> ans;
    string temp;
    stringstream ss(s);
    
    while(getline(ss, temp, del)){
        ans.push_back(temp);
    }
    
    return ans;
}

void dfs(int depth, string now, string route, vector<vector<string>> t){
    if(depth==n){
        list.push_back(route);
        return;
    }
    
    for(int i=0; i<n; i++){
        if(visited[i]) continue; //이미 사용한 티켓
        
        if(now==t[i][0]){
            visited[i] = true;
            dfs(depth+1, t[i][1], route+' '+t[i][1], t);
            visited[i] = false;
        }
    }
}


vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    
    n = tickets.size();
    
    dfs(0, "ICN", "ICN", tickets);

    
    //사전순 정렬
    sort(list.begin(), list.end());
    answer = split(list[0], ' ');

    return answer;
}