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

프로그래머스

[문제 설명]

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

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

제한사항

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

입출력 예

tickets	return
[["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", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

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

---

[문제 풀이]

* 문제에서 주의깊게 봐야하는 부분

1. 항상 "ICN" 공항에서 출발

2. 방문하는 공항 경로를 배열에 담아 return

3. 주어진 항공권은 모두 사용

4. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return

 

4번 조건을 고려하여 입력받은 벡터를 sort함수를 이용하여 정렬해준다.

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

위 처럼 정렬한다면 알파벳 순서가 앞서는 경로 먼저 탐색하게 된다.

 

도착한 공항 경로를 저장할 수 있는 벡터를 하나 준비한다. 

 

1. dfs함수에 시작 공항을 "ICN"을 넣어주고, 해당 티켓의 방문 여부를 isVisited 배열에 저장하고, 공항 경로를 담는 벡터에 넣어준다.

 

2. 만약 방문하지 않은 티켓이라면, 배열의 두번째 인덱스에 저장되어있는 도착 공항을 dfs에 넣어준다.

2.1 만약 공항 경로를 담은 벡터의 크기가 티켓 전체 갯수 +1와 같지 않다면 1번으로 돌아간다.

2.2 만약 공항 경로를 담은 벡터의 크기와 티켓 전체 갯수 +1와 같다면 모든 공항을 순회했다고 생각 할 수 있기에 그만두어도 된다.

 

모든 공항을 다 순회한 후 바로 return해 줄 수 있는 이유는 위에서 우리가 알파벳 순서로 정렬을 해주었기때문이다.

 

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

코드

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

vector<vector<string>> tickets_backup;
vector<bool> isVisited;

bool dfs(vector<string>& answer, string departure)
{
    if(answer.size() == tickets_backup.size()+1)
    {
        return true;
    }

    for(int i =0; i < tickets_backup.size(); i++)
    {
        if(isVisited[i]) continue;
        if(tickets_backup[i][0] == departure)
        {
            isVisited[i] = true;
            answer.push_back(tickets_backup[i][1]);
            if(dfs(answer,tickets_backup[i][1]))
            {
                return true;
            }
            answer.pop_back();
            isVisited[i] = false;
        }
    }
    return false;
}


vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());
    tickets_backup = tickets;
    vector<string> answer;
    isVisited = vector<bool>(tickets.size(), 0);
    answer.push_back("ICN");
    dfs(answer,"ICN");
    return answer;
}