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

1. 문제

 

코딩테스트 연습 - 여행경로 | 프로그래머스 (programmers.co.kr)

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

 

2. dfs

 

 이 문제는 신경써야할 두가지 작은 문제가 있다

 

이를 map 자료구조를 활용하여 쉽게 해결하였다.

 

이 map을 모든 정점과 간선을 탐색하는 dfs돌리면 문제는 해결된다.

 

- 모든 티켓을 사용 

이 문제는 dfs의 일반적인 목적인 정점을 탐색하는 것과 는 다르게  

모든 간선을 지나야하는것이다. 따라서 방문을 기록하는것을 정점이 아니라 간선을 기록해야한다.

 

이런 기록은 map[a][b]에 둠으로써 문제를 해결하였다.

map[a][b]의 값으로 a -> b 로가는 티켓의 개수를 담아 중복된 부분 또한 처리 할 수 있게 하였다.

 

따라서 해당 간선을 방문했으면  map[a][b] 의 값을 -- 해주어 0일시 스킵하도록  하면서 잎노드에 도달할때

모든 간선을 방문했으면 true , 방문하지 못했으면 false를 리턴하여 원상태로 돌려서 탐색을 다시하게 하였다.

 

- 사전순 

여기서 또한 '사전순' 으로 빠른 리스트를 구성해야하는데 

map의 bst를 활용하여 이중 map을 구성한 인접리스트로 나타내어

사전순으로 빠른 정점을 먼저 탐색하도록 하였다.

 

모든 간선을 지나기전에 잎노드에 도달할 경우 해당 간선을 해제하고 구성하고 있던 답을 pop하면

자연스럽게 백트래킹하여 사전순 다음을 탐색하게 해준다.

 

#include <string>
#include <vector>
#include <map>
#include <string>
 
using namespace std;
 
bool dfs(const string& src, int asize, map<string, map<string, int> >& adj, vector<string>& answer) {
    answer.push_back(src);
    if(answer.size() == asize) {
        return true;
    }
    for(auto it = adj[src].begin(); it != adj[src].end(); it++) {
        if(it->second == 0) continue;
        it->second--;
 
        if(dfs(it->first, asize, adj, answer))
            return true;
 
        answer.pop_back();
        it->second++;
    }
 
    return false;
}
vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    map<string, map<string, int> > mps;
    for(auto& t : tickets) {
        mps[t[0]][t[1]]++;
    }
    dfs("ICN", tickets.size() + 1, mps, answer);
    return answer;
}