[DFS, 난이도 중상] 프로그래머즈, 여행경로

여태 백준에서 DFS/BFS 문제를 풀 때는 노드명을 정수로 두고 풀었는데..

노드명이 문자열이라 적응이 잘 안됐다.

C++ vector의 요소들은 정수로된 인덱스로 다룰 수 있는데 , 이번 문제에서는 벡터만으로 풀기에는 꽤 난이도가 있어보였다.

 

그래서 파이썬의 딕셔너리와 유사한 기능을 하는 C++의 map의 도움을 받았다.

map은 key와 value쌍으로 되어있는 구조이다.

하나의 출발점에서 여러 경로로 이동하는 경우를 고려해야 하므로 value에는 여러 요소를 담을 수 있는 vector을 넣기로 했고, 그 vector안에서도 도착점 정보 뿐만아니라 방문 여부까지도 알 수 있게 pair로 도착점, 방문여부 쌍을 이루었다. 

 

모든 도시를 방문 해서 티켓을 모두 소진이 되었음을 확인 할 때 까지 dfs를 수행했다.

도시를 방문 할 때마다

• 방문처리
• answer에 도착지 push
• 티켓 소진 개수 +1

를 해주고 길을 잘못 들었을 경우(티켓은 아직 다 소진을 안했는데 더 이상 갈 경로가 없을 경우) dfs를 빠져나오면서

• 방문처리 취소
• answer에서 pop
• 티켓 소진 개수 -1

를 해주며, 티켓을 모두 소진했을 경우 모든 dfs를 그대로 빠져 나오면 문제가 해결 된다.

answer에는 모두 방문 경로가 담겨져 있기 때문에 dfs를 그대로 모두 전부 리턴해버리면 된다.

 

테스트 케이스 4개 모두 통과

 

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
map<string,vector<pair<string,bool> > > m;
vector<string> answer;
int ticket_count=0;
bool finished=false;

void dfs(string now,int ticket_size){
    for(int i=0;i<m[now].size();i++){
        if(!m[now][i].second){
            m[now][i].second=true;
            answer.push_back(m[now][i].first);
            ticket_count++;
            if(ticket_count==ticket_size){ //모든 티켓을 썼을 경우
                finished=true; 
                return; //이 시점부터 모든 dfs를 리턴한다. 
            }
            dfs(m[now][i].first,ticket_size);
            if(finished) return; //모든 티켓을 썼다면 바로 리턴
            ticket_count--;
            m[now][i].second=false;
            answer.pop_back();
        }
    }
    return;
}
vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(),tickets.end());        
    for(int i=0;i<tickets.size();i++){
        m[tickets[i][0]].push_back(make_pair(tickets[i][1],false));
    }
    answer.push_back("ICN");
    string now = "ICN";
    dfs(now,tickets.size());  
    return answer;
}