프로그래머스 문제 풀이 여행 경로

이 문제는 이시윤 강사님의 프로그래머스 강좌 "파이썬을 무기로, 코딩테스트 광탈을 면하자!"를 보고 정리한 내용입니다.

문제 URL 여행 경로

Contents

1. 문제 지문 파악하기
2. 강사님의 알고리즘 풀이
3. 구르미의 알고리즘 풀이

문제 지문 파악하기

이 문제에서, 우리는 주어진 티켓들을 활용하여 모든 지점을 순회하여야 합니다. 이 때, 알파벳 순서가 앞서는 경로로 만들어주어야 하지요. 언제나 그렇듯이 예제를 통해 문제를 파악해보겠습니다. 2번째 입력을 살펴보죠.

 

tickets :
1. "ICN" -> "SFO"
2. "ICN" -> "ATL"
3. "SFO" -> "ATL"
4. "ATL" -> "ICN"
5. "ATL" -> "SFO"

 

위와 같이 총 5개의 티켓이 있습니다. 문제에서 "ICN"부터 시작하고 알파벳순으로 경로를 만들라고 명시되어 있으니, 2번을 골라야 합니다.

 

path : (2번을 골랐을 때)
ICN -> ATL

 

이제 "ATL"을 시작점으로 하는 티켓들을 봅시다. 4번, 5번 티켓이 있는데, 이 중 알파벳이 앞서는 4번 티켓을 선택합니다.

 

path : (2번 -> 4번을 골랐을 때)
ICN -> ATL -> ICN

 

이제 "ICN"을 시작점으로 하는 티켓 1번을 선택합니다.

 

path : (2번 -> 4번 -> 1번을 골랐을 때)
ICN -> ATL -> ICN -> SFO

 

이제 "SFO"를 시작점으로 하는 티켓 3번을 선택합니다.

 

path : (2번 -> 4번 -> 1번 -> 3번을 골랐을 때)
ICN -> ATL -> ICN -> SFO -> ATL

 

이제 "ATL"을 시작점으로 하는 티켓 5번을 선택합니다.

 

path : (2번 -> 4번 -> 1번 -> 3번 -> 5번을 골랐을 때)
ICN -> ATL -> ICN -> SFO -> ATL -> SFO

 

따라서 이 경로가 답입니다. 이번에는 다른 예제를 살펴봅시다.

 

tickets :
1. "ICN" -> "BOO"
2. "ICN" -> "COO"
3. "COO" -> "ICN"

 

이렇게 되어 있을 때, 어떻게 동작해야 할까요? 먼저 "ICN"을 시작점으로 해서 티켓을 고릅니다. 알파벳 순이닌 1번을 선택해봅시다.

 

path : (1번을 골랐을 때)
ICN -> BOO

 

이 경우, 모든 티켓을 사용하지 않음에도 더 이상 선택할 수가 없습니다. 따라서, 이 경로를 선택하면 안되지요. 그래서 1번을 선택하지 않고 2번을 고릅니다.

 

path : (2번을 골랐을 때)
ICN -> COO

 

이제 3번, 1번을 구하면 원하는 경로를 얻을 수 있지요.

 

path : (2번 -> 3번 -> 1번을 골랐을 때)
ICN -> COO -> ICN -> BOO

 

이제 어떻게 구할지 감이 잡히시나요? 이런 문제들, 각 지점을 모두 순회해야 하는 "완전 탐색"이 필요한 경우, 대체로 DFS 알고리즘을 사용하면 문제를 쉽게 풀 수 있습니다. 이제 문제를 DFS 알고리즘을 활용하여 풀어봅시다.

 

먼저 티켓들을 보고 다음의 그래프를 만들어줍니다. 예제는 문제의 2번째 입력입니다.

 

tickets를 통해 만들어진 그래프 :
routes = {
    "ICN": ["SFO", "ATL"],
    "SFO": ["ATL"],
    "ATL": ["ICN", "SFO"]
}

 

그래프는 해쉬맵 형태로 만들어져 있습니다. 이제 키-값 중 값을 역순으로 정렬합니다. 이유는 나중에 설명드리겠습니다.

 

정렬된 그래프 :
routes = {
    "ICN": ["SFO", "ATL"],
    "SFO": ["ATL"],
    "ATL": ["SFO", "ICN"]
}

 

이제 시작점 "ICN"을 스택에 넣습니다.

 

문제 조건에 따라 "ICN"부터 시작한다.
st = ["ICN"],

routes = {
    "ICN": ["SFO", "ATL"],
    "SFO": ["ATL"],
    "ATL": ["SFO", "ICN"]
}

 

이제 스택에서 가장 맨 위의 데이터를 top이라고 합시다. 우리가 가야 하는 다음 경로는 top을 시작점으로 하는 끝 점들을 역순으로 저장하는 리스트의 가장 마지막 원소가 됩니다. 즉 "ATL"이 되지요. 이 원소를 빼와서 스택에 저장합니다.

 

st = ["ICN", "ATL"],

routes = {
    "ICN": ["SFO"], //"ATL" 빠짐
    "SFO": ["ATL"],
    "ATL": ["SFO", "ICN"]
}

 

이와 같은 과정을 반복합니다.

 

두 번째 :
st = ["ICN", "ATL", "ICN"],
routes = {
    "ICN": ["SFO"],
    "SFO": ["ATL"],
    "ATL": ["SFO"] //"ICN" 빠짐
}

세 번째 :
st = ["ICN", "ATL", "ICN", "SFO"],
routes = {
    "ICN": [], //"SFO" 빠짐 
    "SFO": ["ATL"],
    "ATL": ["SFO"]
}

네 번째 :
st = ["ICN", "ATL", "ICN", "SFO", "ATL"],
routes = {
    "ICN": [],
    "SFO": [], //"ATL" 빠짐
    "ATL": ["SFO"]
}

다섯 번째 :
st = ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"],
routes = {
    "ICN": [],
    "SFO": [],
    "ATL": []  //"SFO" 빠짐
}

 

이제 다음부터는 티켓들이 남아있지 않습니다. 스택의 가장 마지막 원소 "SFO"를 시작점으로 하는 티켓이 존재하지 않기 때문에, 원소를 빼와서 이제 path에 넣습니다.

 

여섯 번째 :
path = ["SFO"],
st = ["ICN", "ATL", "ICN", "SFO", "ATL"], //가장 마지막 원소 SFO 빠짐
routes = { "ICN": [], "SFO": [], "ATL": [] }

 

계속 반복하면 됩니다. 그럼 스택에서 데이터가 모두 빠져나가 path가 역순으로 저장될 것입니다.

 

최종 :
path = ["SFO", "ATL", "SFO", "ICN", "ATL", "ICN"],
st = [],
routes = { "ICN": [], "SFO": [], "ATL": [] }

 

이렇게 해서 얻은 path를 역순으로 돌려주면 됩니다.

 

answer = path[::-1] // ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

 

어떻게 동작하는지 아시겠나요? 바로 코드를 살펴보도록 합시다.

강사님의 알고리즘 풀이

강사님의 알고리즘을 순서대로 표현하면 다음과 같습니다.

1. { 시작점 - [도착점들] } 쌍의 그래프를 만듭니다.
2. 이때 도착점들의 리스트는 역순으로 정렬시킵니다.
3. DFS 알고리즘을 통해서 모든 점을 순회합니다.
   1. 문제 조건에 따라, "ICN"을 스택에 먼저 넣습니다.
   2. 스택이 빌때까지 다음을 반복합니다.
      1. 스택에서 가장 위의 저장된 데이터 top을 꺼내옵니다.
      2. 만약 top이 그래프에 없거나, top을 시작점으로 하는 티켓이 없는 경우, 스택에서 꺼내와 path에 저장합니다.
      3. 2번이 아니라면, top을 시작점으로 하는 끝점 중 가장 마지막 지점을 꺼내와 스택에 저장합니다.
4. 이렇게 해서 얻어온 path를 역순으로 만들어줍니다.

이를 코드로 표현하면 다음과 같습니다.

def solution(tickets):
    # 1. 그래프 생성
    routes = dict()

    for (start, end) in tickets:
        routes[start] = routes.get(start, []) + [end]  

    # 2. 시작점 - [끝점] 역순으로 정렬    
    for r in routes.keys():
        routes[r].sort(reverse=True)

    # 3. DFS 알고리즘으로 path를 만들어줌.
    st = ["ICN"]
    path = []
    
    while st:
        top = st[-1]

        if top not in routes or len(routes[top]) == 0:
            path.append(st.pop())
        else:
            st.append(routes[top][-1])
            routes[top] = routes[top][:-1]
    
    # 4. 만든 path를 거꾸로 돌림.
    answer = path[::-1]
    return answer

 

구르미의 알고리즘 풀이

보통 DFS는 스택을 활용합니다. 우리는 함수 호출 역시 "함수 호출 스택"에 의해서 저장되는 것을 알아야 합니다. 즉, 재귀 함수 호출만으로 DFS를 구현할 수 있습니다. 아래 코드는 재귀 함수로 구현한 DFS 알고리즘을 활용하여 문제를 푼 코드입니다.

 

파이썬 코드

def dfs(graph, N, path, here):
    path.append(here)
    
    if len(path) == N + 1:
        return True
    
    if here not in graph:
        path.pop()
        return False
    
    for i in range(len(graph[here])):
        there = graph[here][-1]
        graph[here].pop()
        
        if dfs(graph, N, path, there):
            return True
        
        graph[here].insert(0, there)
        
    path.pop()
    return False

def solution(tickets):
    routes = dict()

    for (start, end) in tickets:
        routes[start] = routes.get(start, []) + [end]  
    
    for r in routes.keys():
        routes[r].sort(reverse=True)
    
    N = len(tickets)
    path = []
    
    if dfs(routes, N, path, "ICN"):
        answer = path            
        
    return answer

if __name__ == '__main__':
    tickets = [
        ["ICN", "JFK"], 
        ["HND", "IAD"], 
        ["JFK", "HND"]
    ]
    result = solution(tickets)
    print(result)

 

다음은 CPP 코드입니다. 아래 코드는 강사님의 알고리즘을 CPP로 옮긴 것입니다.

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

using namespace std;

vector<string> solution(vector<vector<string>> tickets) {
    map<string, vector<string>> routes;
    
    for (const auto & ticket : tickets) {
        string start = ticket[0];
        string end = ticket[1];
        
        if ( routes.find(start) == routes.end() ) {
            routes[start] = vector<string>();
        }
        
        routes[start].push_back(end);
    }
    
    for (const auto & p : routes) {
        const auto & start = p.first;
        sort(routes[start].begin(), routes[start].end());
        reverse(routes[start].begin(), routes[start].end());
    }
    
    stack<string> st;
    st.push("ICN");
    vector<string> answer;
    
    while (!st.empty()) {
        const auto top = st.top();
        
        if (routes.find(top) == routes.end() || routes[top].size() == 0) {
            answer.push_back(top);
            st.pop();
        } else {
            st.push(routes[top].back());
            routes[top].pop_back();
        }
    }
    
    reverse(answer.begin(), answer.end());
    return answer;
}

int main() {
    vector<vector<string>> tickets = {
        {"ICN", "JFK"}, 
        {"HND", "IAD"}, 
        {"JFK", "HND"}
    };
    auto result = solution(tickets);

    for (const auto & v : result){
        cout << v << " ";
    }
    cout << endl;

    return 0;
}