[프로그래머스] 여행경로 - 풀다가 GG치고 블로그 보고 풀이

https://nanyoungkim.tistory.com/93

[C++] 프로그래머스 Lv.3 - 여행경로(DFS)

 

 

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

 

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

 

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

ticketsreturn

[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

 

 

 

1. 우선 이중벡터를 정렬해주면 배열의 인덱스 순으로 정렬하는 것을 확인할 수 있다.

 

["ICN", "SFO"] 

["ICN", "ATL"]

["SFO", "ATL"]

["ATL", "ICN"]

["ATL","SFO"]

 

-  sort(tickets.begin(), tickets.end());

 

["ATL", "ICN"] ["ATL","SFO"] 이 가장 앞으로 온다. 이중벡터를 많이 사용해 볼 기회가 없었기 때문에

이 부분은 생소했다. 자주 보며 암기가 필요한 부분이다.

 

예제출력)

cout << tickets[0][1]; // ICN
cout << tickets[1][1]; // SFO

cout << tickets.size(); // 첫번째 인덱스의 사이즈를 리턴 

[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]] -> 3

[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] -> 5

 

 

2. 주어진 항공권은 모두 사용해야 합니다.

즉, 입력이 1,2 / 1,3 / 3,1 이라면 (정렬), 1->2까지만 탐색하고 종료해버리는 것이다.

이것을 DFS의 리턴 bool 값을 이용해서 처리해줘야 한다. 탐색을 하다가 끊겼을 경우엔 false 를 리턴해서 가장 뒤의 요소를 pop 하고 다시 탐색을 시작해서 1->2 가 아닌 1->3이 되도록 해준다.

제한사항인 "주어진 항공권은 모두 사용해야 합니다" 를 만족하면 DFS함수를 리턴 시킨다.

 

 

3. 코드

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

using namespace std;

int visited[10000] = {0,}; 
vector<string> res; 

bool dfs(string start, vector<vector<string>> tickets, int cnt){
    
    if(cnt == tickets.size()) return true;
    
    for(int i=0; i<tickets.size(); i++){
        
        if(visited[i] == 0 && start == tickets[i][0]){
            visited[i] = 1;
            res.push_back(tickets[i][1]);
            bool chk = dfs(tickets[i][1], tickets, cnt+1);
            if(chk) return true;             
            visited[i] = false;
        }
    }
    
    res.pop_back();
    return false;
    
    
}


vector<string> solution(vector<vector<string>> tickets) {
    
    vector<string> answer;
    sort(tickets.begin(), tickets.end());
    
    string start = "ICN"; // 항상 "ICN" 공항에서 출발합니다.
    res.push_back(start);
    
    //cout << tickets.size();
    dfs(start,tickets,0);
    
    answer = res;
    
    return answer;
}