프로그래머스 문제 풀이 여행 경로
이 문제는 이시윤 강사님의 프로그래머스 강좌 "파이썬을 무기로, 코딩테스트 광탈을 면하자!"를 보고 정리한 내용입니다.
문제 URL 여행 경로
Contents
- 문제 지문 파악하기
- 강사님의 알고리즘 풀이
- 구르미의 알고리즘 풀이
문제 지문 파악하기
이 문제에서, 우리는 주어진 티켓들을 활용하여 모든 지점을 순회하여야 합니다. 이 때, 알파벳 순서가 앞서는 경로로 만들어주어야 하지요. 언제나 그렇듯이 예제를 통해 문제를 파악해보겠습니다. 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"]
어떻게 동작하는지 아시겠나요? 바로 코드를 살펴보도록 합시다.
강사님의 알고리즘 풀이
강사님의 알고리즘을 순서대로 표현하면 다음과 같습니다.
- { 시작점 - [도착점들] } 쌍의 그래프를 만듭니다.
- 이때 도착점들의 리스트는 역순으로 정렬시킵니다.
- DFS 알고리즘을 통해서 모든 점을 순회합니다.
- 문제 조건에 따라, "ICN"을 스택에 먼저 넣습니다.
- 스택이 빌때까지 다음을 반복합니다.
- 스택에서 가장 위의 저장된 데이터 top을 꺼내옵니다.
- 만약 top이 그래프에 없거나, top을 시작점으로 하는 티켓이 없는 경우, 스택에서 꺼내와 path에 저장합니다.
- 2번이 아니라면, top을 시작점으로 하는 끝점 중 가장 마지막 지점을 꺼내와 스택에 저장합니다.
- 이렇게 해서 얻어온 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;
}