[Programmers] 여행경로

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

풀이

1) 1번 TC만 시간이 328.93ms 으로 다른 TC에 비해 너무 비효율적으로 나왔다. 정답을 받았지만 영 찜찜...

2) 여러 경로가 가능할 경우 알파벳순으로 우선하는 경로가 답이라고 하길래 set에 가능한 경로를 전부 넣은 후 가장 처음에 저장된 경로를 반환했다. (set의 특성상 중복을 제거하며, 오름차순으로 정렬된다.)

3) 처음 시작하는 항공권은 ICN이 출발 공항인 것들을 기준으로 dfs를 호출했다. 

매번 알맞는 최적의 항공권을 찾는 것보다는 그냥 가능하면 모두 호출하도록 했다. 

그 결과는 vector<string> tmp를 매번 가지고 다니면서 가능한 경로를 모두 저장한다. 

4) 항공권을 모두 사용했다면 (cnt == tickets.size()) set에 현재까지 지나온 경로를 넣어준다. 

 

 

#include <string> #include <vector> #include <set> using namespace std; bool chk[10001]; set<vector<string>> s; typedef vector<vector<string>> VVS; void dfs(int cnt, VVS tic, string prev, vector<string> tmp) { if (cnt ==tic.size() ) { s.insert(tmp); return; } for (int i = 0; i < tic.size(); i++) { if (!chk[i] && tic[i][0] == prev) { chk[i ] = true; tmp.push_back(tic[i][1]); dfs(cnt+1, tic, tic[i][1],tmp ); tmp.pop_back(); chk[i] = false; } } } vector<string> solution(vector<vector<string>> tickets) { vector<string> answer; vector<string> tmp; tmp.push_back("ICN"); for (int i = 0; i < tickets.size(); i++) { if (tickets[i][0] == "ICN" && !chk[i]) { chk[i] = true; tmp.push_back(tickets[i][1]); dfs(1, tickets, tickets[i][1], tmp ); tmp.pop_back(); chk[i] = false; } } set<vector<string>> :: iterator it = s.begin(); answer = *it; return answer; }