[프로그래머스] 여행경로

[프로그래머스] 여행경로

코딩테스트 연습 - 여행경로 | 프로그래머스

 

티켓을 가지고 모든 공항을 순회하여야 하고 여러곳을 갈 수 있을경우 알파벳순으로 방문한다.

그리고 모두 방문하지 못하는 경우는 없다.

나는 key - value를 이용할 수 있는 map을 이용하여 티켓별로 갈 수 있는 곳을 지정하였고

value는 리스트로 가지고있어야하니 vector값을 키의 value로 했다

vector는 공항 이름과 방문 여부를 가진 구조체의 벡터로 설정하였다..

그리고 그 value들을 알파벳 순으로 정렬한 뒤

dfs 탐색으로 가장 먼저 나오는 목록을 최종 정답으로 설정하였다.

 

자료구조는 대충 이렇게되어있다

{ "ICN" : {{"ATN", false}, {"SFO", false}}, "SFO" : {{"ATN", false}, {"ICN", false}}, "ATN" : {{"ICN", false}}}

dfs에서 ICN을 시작점으로 하여서

알파벳순으로 하나하나 방문하면서 방문을 했으면 방문 상태를 true로 만들어준다.

모든 곳을 방문하지 못했으면 다시 이전단계로 돌아가면 된다.

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

struct info{
    string name;
    bool visit;
};
map<string, vector<info>> ticket;
vector<string> result;
bool dfs(string begin, int high, int cnt, vector<string> tmp){
    if(cnt == high){
        result = tmp;
        return true;
    }
    for(auto &d : ticket[begin]){
        if(d.visit) continue;
        d.visit = true;
        tmp.push_back(d.name);
        if(dfs(d.name, high, cnt+1, tmp)) return true;
        d.visit = false;
        tmp.pop_back();
    }
    return false;
}
bool sortcomp(info a, info b){
    return a.name < b.name;
}
vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    for(auto t : tickets){
        ticket[t[0]].push_back({t[1], false});
    }
    // 각 티켓, 공항 이름순 정렬
    for(auto &t : ticket){
        sort(t.second.begin(), t.second.end(), sortcomp);
    }
    
    vector<string> tmp = {"ICN"};
    dfs("ICN", tickets.size(), 0, tmp);
    answer = result;
    return answer;
}