여행 경로
-
주어진 항공권을 모두 이용하여 여행경로 짜기
-
항상 “ICN” 공항에서 출발!
-
모든 공항은 알파벳 대문자 3글자로 이루어 진다
-
[a, b] = a공항에서 b공항으로 가는 항공권
-
가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로 return
-
모든 도시를 방문할 수 없는 경우는 주어지지 않음
이렇게 제한사항 및 조건들이 있다.
중요하다고 생각이 드는 것은 모두 이용 키워드와 알파벳 순서 키워드가 있다고 생각한다.
일단 모든 경로를 다 계산해 봐야 된다고 생각했다
-> 알파벳 순서가 앞선다고 greedy 적으로 가다 보면 모두 이용 키워드를 놓칠 수도 있다.
예제를 보자
“SFO” 와 “ATL” 단어를 바꿔보자.
그러면 알파벳 순서 에 따라 가다 보면 막혀 버린다.
ICN -> ATL -> SFO -> ATL -> ???
따라서
-
자신이 갈 수 있는 모든 경로를 다 저장하고
-
마지막에 for문을 이용하여 모든 경로를 dfs 로 검사 하자.
이때 검사하면서 차례대로 vector 에 push_back!
-
dfs로 검사하면서 숫자 counting을 이용해 모든 항공권을 다 썼다면
-
2차원 배열에 1차원 배열을 push_back!
-
모든 경로가 끝났다면 sort를 이용해 알파벳 순서가 앞서는 경로 return!
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<string>> ans;
void go(vector<vector<string>> tickets, vector<bool>visited, int index,int isit,vector<string> temp) {
visited[index] = true;
string from = tickets[index][1];
temp.push_back(from);
vector<int> to;
if (isit == tickets.size()) { // 모든걸 다 썼다면
ans.push_back(temp);
}
for (int i = 0; i < tickets.size(); i++) {
string tempFrom = tickets[i][0];
string tempTo = tickets[i][1];
if (!visited[i] && tempFrom == from) { // 시작하는 위치이고, 티켓을 사용하지 않았다면
to.push_back(i);
}
}
for (int i = 0; i < to.size(); i++) // 모든 길 검사해주기
go(tickets, visited, to[i], isit + 1,temp);
}
vector<string> solution(vector<vector<string>> tickets) {
vector<int>to;
int index = 0;
for (int i = 0; i < tickets.size(); i++) {
string tempFrom = tickets[i][0];
string tempTo = tickets[i][1];
if (tempFrom == "ICN") {
to.push_back(i);
}
}
vector<bool>visited;
visited.resize(10001);
vector<string>temp;
temp.push_back("ICN");
for(int i=0;i<to.size();i++)
go(tickets, visited, to[i],1,temp);
sort(ans.begin(), ans.end());
return ans[0];
}
