https://programmers.co.kr/learn/courses/30/lessons/43164
접근
처음에 dfs가 아니라 해쉬로 접근하려 했습니다.
ticket의 출발지점을 key로 도착지점을 value로 가지는 해쉬맵을 만들고
만약 출발지점이 같지만, 도착지점이 다른 티켓이 있을 경우를 대비해서 value를 vector으로 선언했습니다.
2개 이상의 루트가 존재하면 알파벳 순으로 여행해야 하므로 저 vector의 길이가 2 이상이라면 정렬만 하면 된다고 생각했으나 ...
접근2
50.0점이 나왔습니다. 애초에 그렇게 쉬울 것 같지도 않았습니다.
문제는 그때그때 알파벳순으로 여행하는것이 꼭 최선의 경로가 아니라는 점 이었습니다.
무조건 알파벳순으로 여행하면, 모든 티켓을 사용하지 않았음에도 더 이상 여행할곳이 없는 경우가 생깁니다. 따라서 백트랙킹으로 되돌아가야 하는 문제였습니다.
계속 세그 폴트가 뜨길래 처음엔 티켓이 너무 많나 라고도 생각했습니다.
실제로 여행지의 개수제한만 있지, 티켓의 제한은 없고, 모든 여행지를 돌아다닐수 있게만 티켓이 주어지기 때문에
티켓은 무한대가 가능합니다.
예를 들어 여행지가 1,2,3이 있다면
1->2 , 2->1 이런 티켓이 1000억개가 있고 2->3 티켓이 하나 있기만 하면 모든 조건이 만족됩니다..
조건에 티켓 개수의 제한이라도 있었으면 하는 바램이었습니다.
아무튼 세그폴트나 런타임 에러가 나는건 티켓장수의 문제가 아니라
알파벳 순으로 진행하다보면 더 이상 진행할 수 없음에도, 무조건 티켓장수 만큼 여행을 해야하기에
잘못된 메모리 참조가 일어나는 것 이었습니다.
다음부터는.. 풀기 전에 최대한 많은 예외를 생각해봐야 겠습니다. 실제 테스트에서는 제가 틀린줄도 몰랐을테니까요
다음은 코드 전문입니다.
#include <string>
#include <vector>
#include <unordered_map>
#include <utility>
#include <algorithm>
using namespace std;
unordered_map<string, vector<string>> src_dst;
unordered_map<string, int> un_used;
vector<string> path;
vector<vector<string>>* t;
bool dfs(string src);
vector<string> solution(vector<vector<string>> tickets) {
t = &tickets;
for(int i = 0 ; i < tickets.size(); i++){
src_dst[tickets[i][0]].push_back(tickets[i][1]);
un_used[tickets[i][0]+tickets[i][1]] += 1; // need to check
}
path.push_back("ICN");
dfs("ICN");
return path;
}
bool dfs(string src){
bool isFail = true;
if ((t->size())+1 == path.size()) {
return true;
}else if(src_dst[src].empty()){
return false;
}else{
if (src_dst[src].size() > 1 ) {
sort(src_dst[src].begin(),src_dst[src].end());
for(int j = 0 ; j < src_dst[src].size(); j++){
if (un_used[src+src_dst[src][j]] != 0) {
path.push_back(src_dst[src][j]);
un_used[src+src_dst[src][j]] -= 1;
if(!dfs(src_dst[src][j])){
isFail = true;
path.pop_back();
un_used[src+src_dst[src][j]] += 1;
}else{
isFail = false;
break;
}
}
}
}else{
path.push_back(src_dst[src][0]);
un_used[src+src_dst[src][0]] -= 1;
if(!dfs(src_dst[src][0])){
un_used[src+src_dst[src][0]] += 1;
path.pop_back();
isFail = true;
}else{
isFail = false;
}
}
}
if (isFail) {
return false;
}
else return true;
}