[C++][프로그래머스] 여행경로 :: seoftware

 

문제

---

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

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

 

제한사항

 

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

 

입출력 예

 

tickets	return
[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]]	[ICN, ATL, ICN, SFO, ATL, SFO]
[[ICN, JFK], [HND, IAD], [JFK, HND]]	[ICN, JFK, HND, IAD]

 

입출력 예 설명

 

예제 #1

[ICN, JFK, HND, IAD] 순으로 방문할 수 있습니다.

예제 #2

[ICN, SFO, ATL, ICN, ATL, SFO] 순으로 방문할 수도 있지만 [ICN, ATL, ICN, SFO, ATL, SFO] 가 알파벳 순으로 앞섭니다.

 

---

 

사용 알고리즘

DFS + 백트래킹


백트래킹은 DFS의 효율을 높이기 위해 가지치기(pruning)을 한 것

 

---

 

소스코드 - 전체 & 설명

---

전체 소스코드 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int n;
bool dfs(vector<vector<string>> const tickets, vector<string> &route, vector<bool> &visited, string dst){
    route.push_back(dst);
    if(route.size() == n+1) return true;
    for(int i = 0; i<n; i++){
        if(!visited[i] && tickets[i][0] == dst){
            visited[i] = true;
            if(dfs(tickets, route, visited, tickets[i][1])){
                return true;
            }
            visited[i] = false;
        }
    }
    route.pop_back();
    return false;
}
vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    n = tickets.size();
    sort(tickets.begin(), tickets.end());
    for(int i = 0; i < n; i++){
        vector<bool> visited(n, false);
        vector<string> route;
        if(tickets[i][0] == "ICN"){
            visited[i] = true;
            route.push_back("ICN");
            if(dfs(tickets, route, visited, tickets[i][1])){
                answer = route;
                break;
            }
            
        }
    }
    return answer;
}

 

---

자세한 풀이

 

1. [solution] tickets를 sort 하여 알파벳 순서대로 경로를 찾도록 한다.

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

 

2. [solution] DFS를 이용하여 경로를 탐색하기 위해 visited 배열과 임시로 경로를 담아두는 배열인 route를 선언한다.

vector<bool> visited(n, false);
vector<string> route;

 

3. [solution] tickets의 첫 번째 요소(출발지)가 "ICN"인 경우 visited[i]를 true로 바꾸고, route에 "ICN"을 넣은 후 dfs 함수를 호출한다.

dfs 함수는 route의 요소가 tickets의 요소보다 1개 더 많아지면 true를 return 한다. 따라서 조건문이 수행되는 것은 정답을 찾았다는 의미이므로 answer에 route를 대입하고 반복문을 종료한다.

if(tickets[i][0] == "ICN"){
    visited[i] = true;
    route.push_back("ICN");
    if(dfs(tickets, route, visited, tickets[i][1])){
    	answer = route;
    	break;
    }      
}

 

 

5. [dfs 함수] route에는 최초 출발지만 들어있는 상태다. route에 도착지(dst)를 넣는다.

route.push_back(dst);

 

6. [dfs 함수] route의 요소 개수가 n+1 개가 되면 true를 return 한다. 

if(route.size() == n+1) return true;

 

7. [dfs 함수] dst가 이전에 방문한 곳이 아닐 경우에 dfs 함수를 재호출한다(재귀).

true를 반환한다는 것은 경로 탐색이 끝났다는 의미이므로 return true를 반복하여 처음 dfs 함수를 호출한 곳인 solution 함수로 돌아간다. 

false를 반환한다는 것은 i번째 도시를 다음 출발지로 지정했을 때 길이 없음을 의미하므로 visited[i]를 다시 false로 바꿔주고 다른 도시를 찾는다.

if(!visited[i] && tickets[i][0] == dst){
	visited[i] = true;
	if(dfs(tickets, route, visited, tickets[i][1])){
		return true;
	}
	visited[i] = false;
}

 

8. [dfs 함수] for문이 반복될 동안 true를 return 하지 못했다는 것은 그 길은 경로가 될 수 없음을 의미하므로 가지치기를 해준다(백트래킹). 넣었던 dst를 제거하고 false를 return 한다.

route.pop_back();
return false;