프로그래머스 여행경로 c++

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

보자마자 또 문제 잘못보고 map으로 풀었다. 아차차 다시 ICN왔다갔다 할 수 있다.

#include <string> // 실패코드
#include <vector>
#include <unordered_map>

using namespace std;

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    unordered_map<string, string> m;
    for (int i = 0; i < tickets.size(); i++)
        m[tickets[i][0]] = tickets[i][1];
    string cur = "ICN";
    answer.push_back("ICN");
    for (int i = 0; i < tickets.size(); i++) {
        answer.push_back(m[cur]);
        cur = m[cur];
    }
    return answer;
}

 

결국 모든 경우를 다 탐색하는 dfs로 풀어야 한다.

혹시 시간 초과가 날까 싶어 tickets vector를 도시별로 sort해 놓았으니, 각 도시별 tickets vec 시작 인덱스를 map으로 기억해 두었다. 

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

using namespace std;
vector<string> answer;
unordered_map<string, int> m; // 도시별 티켓의 인덱스
vector<vector<string>> tickets;
vector<bool> visit(10001, false);
int ticket_size;
bool find_flag = false;

void dfs(int cnt, string city) {
    answer.push_back(city);
    if (cnt == ticket_size) { // 다 찾았다
        find_flag = true;
        return;
    }
    for (int i = m[city]; i < ticket_size && city == tickets[i][0]; i++) {
        if (visit[i] == true)
            continue ;
        visit[i] = true;
        dfs(cnt + 1, tickets[i][1]);
        if (find_flag) // 다 찾았으니까 이제 남은 재귀스택 다 종료시켜야 한다. 더이상 탐색 ㄴ
            return;
        visit[i] = false;
    }
    answer.pop_back();
}

vector<string> solution(vector<vector<string>> ticket) {
    tickets = ticket;
    sort(tickets.begin(), tickets.end());
    ticket_size = tickets.size();
    for (int i = 0; i < ticket_size; i++) {
        if (m.find(tickets[i][0]) == m.end()) // 도시별로 시작 idx 기억해둔다
            m[tickets[i][0]] = i;
    }
    dfs(0, "ICN");
    return answer;
}

 

매번 문제이해를 못하는데 이거 어카지... 독서를 해야 하나...? ㅠㅜ