프로그래머스 (깊이/너비 우선 탐색; 여행경로) c++

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

using namespace std;

vector<string> answer;
vector<bool> used;

bool dfs(vector<vector<string>>& tickets, vector<string>& path, string current, int ticketCount)
{
    if(path.size() == ticketCount + 1)      // 모든 티켓을 사용했으면
    {
        answer = path;
        return true;
    }
    
    for(int i = 0; i < tickets.size(); ++i)
    {
        if(used[i]) continue;
        if(tickets[i][0] != current) continue;
        
        used[i] = true;
        path.push_back(tickets[i][1]);
        
        if(dfs(tickets, path, tickets[i][1], ticketCount)) return true;      // 성공하면 바로 종료
        
        path.pop_back();
        used[i] = false;
    }
    
    return false;
}

vector<string> solution(vector<vector<string>> tickets) 
{
    sort(tickets.begin(), tickets.end());
    
    used.assign(tickets.size(), false);
    vector<string> path;
    path.push_back("ICN");      // 항상 ICN에서 출발
    
    dfs(tickets, path, path[0], tickets.size());
    
    return answer;
}

 

해설:

dfs로 깊이 탐색.