프로그래머스 - 여행경로

 이 문제는 DFS를 이용하는 Level 3 문제이다. 이 문제에서 핵심은 티켓이 중복될 수 있다는 것과, 정점의 방문 여부와 상관없이 간선이 모두 소진되어야 DFS가 종료되어야 한다는 것이다. 또한 DFS 실행 도중 언제 result에 현재 정점을 넣을 건지도 굉장히 중요하다. 경로가 다양할 경우 알파벳 순서로 앞에 오는 경로부터 선택해야 하므로 ticket[1] 에 대해서 sort를 수행한 뒤 DFS를 실행한다. 보통은 인접 리스트로 그래프를 구현하지만, 이 문제의 조건인 간선의 모든 소진을 만족하도록 직관적으로 구현했다. 처음에는 dfs 초기에 result에 현재 노드를 삽입했지만, 이는 테스트 케이스 1번과 2번에서 오답이 나온다. 위상 정렬 알고리즘처럼 맨 마지막에 result를 삽입하고 그 결과를 reverse 한 결과 모두 맞을 수 있었다.

 

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

using namespace std;

typedef struct _edge
{
    string start;
    string end;
    bool used = false;
} edge;

vector<edge> edges;
vector<string> result;

bool compare(edge& a, edge& b)
{
    return a.end < b.end;
}

void dfs(string start)
{
    for (int i = 0; i < edges.size(); i++)
    {
        edge& temp = edges[i];
        
        if (temp.start == start && !temp.used)
        {
            temp.used = true;
            dfs(temp.end);
        }
    }
    
    result.push_back(start);
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    
    for (auto ticket : tickets)
    {
        edge temp = {ticket[0], ticket[1], false};
        edges.push_back(temp);
    }
    
    sort(edges.begin(), edges.end(), compare);
    
    dfs("ICN");
    
    reverse(result.begin(), result.end());
    
    answer = result;
    
    return answer;
}