[c++] 프로그래머스 - 여행경로(Level 3)

문제

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

 

코드

#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <iostream>

using namespace std;

struct Info{
    string city;
    int index;
};

unordered_map<string, vector<Info>>graph;
bool flag = true;
vector<string>answer;
int visited[10001];

void dfs(string now, int move, vector<string>memory, int len){
    if(move == len&&flag){
        flag = false;
        answer = memory;
        return;
    }
    
    for(int i=0; i<graph[now].size(); i++){
        if(visited[graph[now][i].index]) continue;
        visited[graph[now][i].index] = 1;
        memory.push_back(graph[now][i].city);
        dfs(graph[now][i].city, move+1, memory, len);
        memory.pop_back();
        visited[graph[now][i].index] = 0;
    }
}
vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());
    
    for(int i=0; i<tickets.size(); i++){
        string a = tickets[i][0];
        string b = tickets[i][1];
        graph[a].push_back({b,i});
    }
    
    dfs("ICN", 0, {"ICN"}, tickets.size());
    
    return answer;
}

 

풀이

다음과 같은 입력을 조심해야 하는데 {{"ICN","AAA"},{"ICN","AAA"},{"ICN","AAA"},{"AAA","ICN"},{"AAA","ICN"}} 와 같이 중복된 티켓이 있을 때 처리를 잘해주지 않으면 채점 데이터 1번에서 계속 틀리게 됩니다.

귀찮아서 안풀던걸 한 번에 싹 풀어버리니 속 시원하네요