프로그래머스 - 여행경로 - C++

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

 

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

unordered_map<string,vector<string>> graph;
vector<string> answer;
bool dfs(string node, int cnt,int total)
{
    if(cnt==total)
        return true;
    
    for(int i=0;i<graph[node].size();i++)
    {
        string next = graph[node][i];
        
        graph[node].erase(graph[node].begin()+i);
        answer.push_back(next);
        
        if(dfs(next,cnt+1,total))
            return true;
        
        answer.pop_back();
        graph[node].insert(graph[node].begin()+i,next);
    }
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    
    for(auto& item : tickets)
        graph[item[0]].push_back(item[1]);
    
    for(auto& item : graph)
        sort(item.second.begin(),item.second.end());
    
    answer.push_back("ICN");
    dfs("ICN",0,tickets.size());
    
    return answer;
}

이 문제는 주어진 티켓들을 모두 사용하여 경로를 완성하는데 완성되는 경로중 사전순으로 가장 빠른 경로를 리턴하는 문제이다. 

 

즉, 경로가 완성되는 경로를 전부 따져보고 그 중 하나를 골라야한다. 

완전탐색과 비슷하게 재귀함수를 이용한 dfs로 풀면 쉽게 접근할 수 있다. 

 

unordered_map<string,vector<string>> graph;

for(auto& item : tickets)
        graph[item[0]].push_back(item[1]);
    
    for(auto& item : graph)
        sort(item.second.begin(),item.second.end());

먼저 graph를 생성한다. 

각 노드에 대해서 인접노드를 vector<string>에 저장한다. 

그리고 인접노드를 사전순으로 정렬한다. 정렬을 하는 이유는 탐색시간을 줄이기 위함이다.

 

answer.push_back("ICN");
    dfs("ICN",0,tickets.size());

시작은 반드시 ICN이니 answer에 ICN를 넣고 dfs 를 시작한다. 

 

bool dfs(string node, int cnt,int total)
{
    if(cnt==total)
        return true;
    
    for(int i=0;i<graph[node].size();i++)
    {
        string next = graph[node][i];
        
        graph[node].erase(graph[node].begin()+i);
        answer.push_back(next);
        
        if(dfs(next,cnt+1,total))
            return true;
        
        answer.pop_back();
        graph[node].insert(graph[node].begin()+i,next);
    }
    return false;
}

먼저 cnt는 현재 사용한 티켓수고 total은 전체 티켓수이다. 즉 이 둘이 동일하다면 경로가 완성된 것이다. 

그리고 for문에서 각 노드에 인접노드들을 하나씩 경로에 추가해보며 경로가 완성되는지 확인한다. 

즉, next를 경로에 넣고 다음 재귀호출을 시도한다. 

 

재귀호출을 완료하고 만약 경로가 만들어지지 않았다면 false가 리턴되고 다시 원상태로 복귀시킨다. 

 

이 재귀함수는 경로가 가장 처음 완성되었을 때 리턴한다는 가정이 있다. 왜냐하면 그게 가장 사전순으로 빠른 경로일 것이기 때문이다. 그래서 경로를 따로 저장해두고 최댓값비교라던지 하는 과정을 거치치 않는 것이다.