[프로그래머스] 여행경로

여행경로

 

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 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] 가 알파벳 순으로 앞섭니다.

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector <vector<string> > vT;
int sizeOfVector;
int ch[10000001];
vector <string> routes;
vector <vector <string> > sol;

bool comp(const vector <string> &a,const vector <string> &b){
    if (a[0] < b[0])
        return true;
    else if(a[0] > b[0])
        return false;
    else if (a[0] == b[0])
    {
        if (a[1] < b[1])
            return true;
        else 
            return false;
    }
}

void DFS(string start, int n)
{
    if (n == sizeOfVector)
    {
        sol.push_back(routes);
    }
    else
    {
        for (int i = 0; i < sizeOfVector; i++)
        {
            if (ch[i] == 0 && vT[i][0] == start)
            {
                ch[i] = 1;
                routes.push_back(vT[i][1]);
                DFS(vT[i][1], n + 1);
                ch[i] = 0;
                routes.pop_back();
            }

        }
    }

}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;

    sort(tickets.begin(), tickets.end(), comp);
    vT = tickets;

    sizeOfVector = tickets.size();

    routes.push_back("ICN");
    DFS("ICN", 0);
    return sol[0];
}

해당 문제는 DFS를 이용한다.

DFS는 기본적으로 우리가 멈춰줘야 할 level이 존재한다.

 

조건에 알파벳 순서로 정렬하라고 했기 때문에 정렬해본다.

 

[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]]의 예시를 살펴보자.

이 순서는 sort에 의해 정렬된다.

bool comp(const vector <string> &a,const vector <string> &b){
    if (a[0] < b[0])
        return true;
    else if(a[0] > b[0])
        return false;
    else if (a[0] == b[0])
    {
        if (a[1] < b[1])
            return true;
        else 
            return false;
    }
}

사실 기본 sort함수를 써도 정렬이 잘 되지만 연습을 위해서

정렬을 했다.

정렬 기준은 다음과 같다.

 

출발지점을 오름차순(문자기 때문에 사전순)으로 정렬한다.

출발지점이 같다면 도착지점을 오름차순으로 정렬한다.

 

정렬된 배열은 다음과 같다.

 

[ATL, ICN] , [ATL,SFO] , [ICN, ATL] , [ICN, SFO] , [SFO, ATL]

 

우리는 무조건 ICN에서 출발한다.

DFS("ICN",0);

그렇기 때문에 main solution에서 다음과 같이 선언한다.

 

routes stack에는 ICN하나만 쌓인다.

 

그리고 DFS구현을 보자,  

n은 우리가 최대로 가야할 level을 의미한다.

n이 5가 아니기 때문에

else문에서

배열 전체를 for문으로 읽고

ch(이미 DFS가 읽었는지 확인)가 0인 값이고 start가 ICN인 배열값을 찾는다.

 

void DFS(string start, int n)
{
    if (n == sizeOfVector)
    {
        sol.push_back(routes);
    }
    else
    {
        for (int i = 0; i < sizeOfVector; i++)
        {
            if (ch[i] == 0 && vT[i][0] == start)
            {
                ch[i] = 1;
                routes.push_back(vT[i][1]);
                DFS(vT[i][1], n + 1);
                ch[i] = 0;
                routes.pop_back();
            }

        }
    }

}

다음 배열에선 ATL이 가장 먼저 선택된다.

그럼 ch값을 1로 변경시켜 준 뒤 다음 DFS로 이동

[ATL, ICN] , [ATL,SFO] , [ICN, ATL] , [ICN, SFO] , [SFO, ATL]

     0             0               1              0               0

 

---

DFS("ATL" 0+1);

스택은 다음과 같다 Lv는 1이다.

이제 다시 for문을 돌며

시작점이 ATL이고 ch가 되지 않은 첫번째 배열 값의 도착지를 다시 스택에 쌓아준다.

그리고 해당 배열값의 ch를 1로 변경시켜준다. (이겨선 [ATL,ICN]이 선택)

 

[ATL, ICN] , [ATL,SFO] , [ICN, ATL] , [ICN, SFO] , [SFO, ATL]

     1             0               1              0               0

---

DFS("ICN" 1+1);

스택은 다음과 같다. 

lv=2

ICN으로 시작하고, ch가 0인 처음 값을 선택

 

[ATL, ICN] , [ATL,SFO] , [ICN, ATL] , [ICN, SFO] , [SFO, ATL]

     1             0               1              1               0

---

DFS("SFO" 2+1);

스택은 다음과 같다.

lv =3

 

 

이걸 마지막까지 반복하면...

 

이런 스택이 완성되고 lv가 5가된다. 이 때, 처음 완성된 값이

알파벳 순서가 가장 빠른 여행경로이다.

이 경로를 sol에 push_back해준다.

 

 

그리고 DFS에서 한번씩 빠져나올 때는 

                ch[i] = 0;
                routes.pop_back();

DFS 다음 명령줄에 의해서 ch를 다시 1에서 0으로 바꿔주고 (다음 연산에서 '사용하지 않음' 취급하고 이용하기 위함)

routes stack에선 빼준다.

 

우리가 구하는 건 여러 경로 중.

알파벳 순서가 가장 빠른 것이므로

 

sol[0]을 정답으로 출력해주면 된다.

 

 

 

 

---

 

DFS를 공부할 수 있고

vector의 comp를 선언을 공부할 수 있는 좋은 문제.