프로그래머스 : 여행경로

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

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

 

​

처음에 BFS로 구현했다가, 백트래킹 과정이 누락된걸 확인하고 DFS로 재구현하였습니다.

도착지 알파벳 순으로 정렬한 뒤, 현재 출발지로 이동할 수 있는 티켓을 통해 DFS로 경로를 찾아주었습니다.

 

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

bool compare(const vector<string>& a, const vector<string>& b) {
    return a[1] < b[1];
}

bool dfs(const string& cur, vector<vector<string>>& tickets, vector<bool>& visit, vector<string>& answer) {
    answer.push_back(cur);
    if(answer.size() == tickets.size() + 1) {
        return true;
    }
    for(int i=0; i<tickets.size(); i++) {
        if(tickets[i][0] == cur && !visit[i]) {
            visit[i] = true;
            if(dfs(tickets[i][1], tickets, visit, answer)) return true;
            visit[i] = false;
        }
    }
    answer.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<bool> visit(tickets.size(), false);
    sort(tickets.begin(), tickets.end(), compare);
    dfs("ICN", tickets, visit, answer);
    return answer;
}