[프로그래머스] 여행경로 (C/C++)

문제 링크 : programmers.co.kr/learn/courses/30/lessons/43164

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

전형적인 DFS 방식으로 문제를 풀었다.

visited를 tickets+1의 크기만큼 만들고 visited와 answer를 참조로 받아 DFS 방식으로 돌렸다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

bool dfs(string here, vector<int>& visited, vector<vector<string>> tickets, vector<string>& answer) {
	answer.push_back(here);

    for(vector<vector<string>>::iterator iter = tickets.begin(); iter != tickets.end(); iter++) {
        int idx = iter - tickets.begin();
        
        if(visited[idx] == false && (*iter)[0] == (*(answer.end() - 1))) {
            visited[idx] = true;

            bool check = dfs((*iter)[1], visited, tickets, answer);

            if(check) {
                return true; 
            } else {
                visited[idx] = false; 
            }
        }
    }
    
    if(int(tickets.size()) == int(answer.size()) - 1) {
        return true; 
    }

    answer.pop_back();

    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;

    vector<int> visited(tickets.size());
	sort(tickets.begin(), tickets.end());

	dfs("ICN", visited, tickets, answer);

	return answer;
}