문제
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "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"] |
풀이
전형적인 DFS 문제이다. 그래프가 아닌데 왜 DFS 문제인지 의문이 든다면 이전 포스팅을 참고하면 좋을 것 같다.
출발 노드는 "ICN"으로 항상 고정이다. 그리고 현재 노드와 연결된 다음의 노드는 항상 주어진 배열의 두 번째 원소이다. 즉 현재 노드와 연결이 된 노드를 우선순위로 탐색하며 정답을 찾는 과정이 요구되므로 이는 깊이 우선 탐색(DFS) 방식과 굉장이 흡사하다고 볼 수 있다.
다만 주의할 것은 문제의 조건에 의해 현재 출발역이 여러개가 들어오는 경우엔 알파벳 순으로 앞서는 도착역을 우선 방문해야 한다. 또한 문제 조건에 의해 모든 도시를 방문할 수 없는 여부는 주어지지 않기 때문에 이에 대한 처리는 신경쓰지 않아도 된다.
DFS는 재귀적으로 구현하는 방법과 Stack으로 구현하는 방법이 있다. 위에 링크를 건 포스팅에서도 잠깐 말했지만 JS에서 DFS 구현에는 다른 언어보다 주의해주어야 할 점이 여럿 있다. 보통 DFS 는 구현의 편의를 위해 재귀적으로 많이 구성하는데 우리의 JS께서는 재귀함수의 호출스택을 잘 버티지 못한다. 이에 대해서 나름의 이유가 있는데 관련 내용은 추후 기회가 되면 다루어보도록 하겠다. 때문에 만약 재귀로 DFS를 구현하고자 하는데 문제의 제한 사항을 잘 보니 데이터의 양이 방대하여 재귀의 깊이가 깊어질 것 같다면 Stack으로 구현하는 것을 추천한다. 다만 해당문제에는 재귀적으로 구현하더라도 주어진 공항의 수가 10000개 이하이기 때문에 이 정도쯤은 JS로도 크게 문제가 없다. 때문에 재귀적으로 DFS를 구현해보자.
python 같은 경우는 import sys 하여 sys.setrecursionlimit()을 통해 직접 재귀호출의 limit을 설정할 수 있고, 알고리즘으로 많이 선택하는 언어 중에 하나인 C++은 재귀호출의 Maximum limit이 기본적으로 인터프리터 형식의 JS에 비해 상대적으로 더 높다... (때
문에 알고리즘을 굳이 JS로 풀이하려는 고집을 부리지 않는 것을 추천한다)
다시 본론으로 돌아와서 가장 먼저 선행해야할 작업은 주어진 여행티켓을 정렬해주어야 한다. 앞서 JS에 대해 계속 험담을 해왔지만 이 부분만큼은 JS의 정렬 함수가 굉장히 편리한데, 직접 코드로 확인하자.
// js : sort() 함수 호출하면 끝
tickets.sort();
// python
sorted(tickets, key = lambda x : (x[0], x[1]))
// c++
bool compare(vector<string> a, vector<string> b)
{
return a[1] < b[1];
}
sort(tickets.begin(), tickets.end(), compare);
// Java
Collections.sort(result, new Comparator<Stack<String>>() {
@Override
public int compare(Stack<String> o1, Stack<String> o2) {
for (int i = 0; i < o1.size(); i++) {
String s1 = o1.get(i);
String s2 = o2.get(i);
if (!s1.equals(s2)) {
return s1.compareTo(s2);
}
}
return 0;
}
});물론 다른 언어의 경우 다른 방법으로도 구현할 수 있겠지만, 다른 사람의 풀이에서 가장 처음에 링크된 정렬 과정을 가져와봤다. JS를 제외하곤 뭔가 조건으로 던져주는 것이 하나 이상씩은 있는 것을 확인할 수 있다.
우리는 주어진 조건 알파벳 순서가 앞서는 경로를 return이라는 문구 때문에 주어진 tickets 배열을 다음과 같이 정렬해줄 것이다.
- 먼저 출발역
tickets[0]을 기준으로 오름차순 정렬 - 만일 출발역이 동일하면 도착역
tickets[1]을 기준으로 오름차순 정렬
- 문자를 오름차순 정렬한다면 알파벳 순 정렬이 된다!
위와 같이 정렬을 해준다면, 우리가 DFS로 탐색을 진행할때 순차적으로 연결된 노드에 방문해도 문제의 조건을 충족할 수 있을 것 이다. 이 과정에서 2번의 조건 때문에 정렬함수(JS에서는 sort)에 해당 조건을 넣어주어야 한다.
하지만 JS의 경우 sort() 함수는 기본적으로 문자열을 오름차순 정렬해준다. ( 이는 숫자를 원소로 가진 배열을 정렬할 때는 또 나름 귀찮은데 해당 문제에서는 또 장점이 되기도 하니 매우 아이러니 하다. ) 그런데 거기서 그치지 않고, 문제의 경우처럼 주어진 배열이 2차원 배열인 경우 자기가 알아서 2번의 조건을 적용하여 정렬을 완성해준다! 즉 JS 에서는 위에서 언급한 1번과 2번의 조건의 sort() 함수의 default로 지정이 되어있다. 때문에 우리는 그저 tickets 를 정렬해주기만 하면 되는 것 이다.
물론 다른 조건으로 정렬해야 한다면 JS에서도 튜닝을 해주어야 한다.
주저리 주저리 말이 길어졌지만, 어찌됐든 중요한 것은 tickets 를 위 조건대로 정렬해주어야 하는 이유와 정렬해주는 방법에 대해 살펴보았다.
그렇다면 DFS를 재귀적으로 구현해보자. 재귀적으로 구현하는 것 역시 특정 값을 반환하도록 구현하는 경우, 또는 반환값이 없는 형태로 구현하는 경우 등 다양하게 나눌 수 있다. 여기서는 true 와 false 값을 반환하도록 만들어 결과값을 구성할 수 있도록 해 줄 것이다.
먼저 DFS 함수에 전달할 인자는 현재 출발역(= str)과 방문역의 개수(= count)를 줄 것이다. 만약 전달받은 count가 tickets의 길이와 일치하는 경우 모든 역을 방문했다는 뜻이 될 것이므로 이 경우 return true를 해줄 것 이다. 이를 코드로 보면 다음과 같다. 즉 재귀함수가 무한 반복되게끔 할 수 없으므로 탈출 조건을 만들어주는 것과 같다.
const answer = [];
const result = []; // result에는 DFS를 돌면서 그때그때 방문하는 역들이 들어있게 될 것이다.
const len = tickets.length;
const dfs = (str, count) => {
result.push(str); // 일단 해당역을 리스트에 삽입한다
if(count === len) {
answer = result;
return true;
// 재귀함수이므로 break 가 아니라 return을 하는 것에 주의하자
}
...
}탈출 조건을 만들어 주었으니 실제 DFS 탐색의 로직을 구현해보자. 이 시점에서 tickets 는 이미 정렬이 되어있으므로 앞에서부터 반복문을 돌면서 현재 차례의 tickets 원소의 출발역이 주어진 str과 일치하고 동시에 해당 역을 아직 방문하지 않았다면 다시 DFS 를 호출하는 식이 될 것이다.
이때 중요한 것은 먼저 해당 역은 방문하지 않았기 때문에 방문 처리를 해주고 DFS를 다시 호출하는 것 이다. 우리는 앞서서 DFS의 반환값을 참/거짓으로 설정해주었기 때문에 호출된 결과가 true 라면 역시 해당 단계에서도 true를 해주어 정상적인 종료를 유도할 수 있다.
만약 이때, DFS의 반환값이 거짓으로 나온다면 이는 해당 단계에서 DFS 탐색으로 계속 내려가며 마지막 deps까지 진행했음에도 불구 아직 방문하지 못한 노드가 있다는 의미와 같다. 이 경우에는 성공적인 DFS 탐색을 마치지 못했기 때문에 false를 반환해주어야 할 것 이다. 그 전에 우리가 방문처리해준 노드를 다시 방문하지 않은 상태로 바꾸어 주어야 한다. 이 과정이 DFS에서 중요한 과정인데, 이를 생략하면 다른 노드를 기준으로 DFS 를 다시 돌아야할 때 정상적으로 다른 경로의 탐색을 수행할 수 없다. 또한 return false를 해주기 전에 우리가 DFS 초반에 result에 현재역을 push 해주었는데, 이는 정상적인 경로가 아니므로 이 역시 다시 제거를 해주어야 한다. 이를 코드로 구현하면 다음과 같다.
...
const dfs = (str, count) => {
result.push(str);
if(count === len) {
answer = result;
break;
}
for(let i = 0; i < len; i++) {
if(!visited[i] && tickets[i][0] === str) {
visited[i] = true; // 현재노드 방문처리
// 다음 dfs 진행은 현재 노드의 도착역이 기준이 될 것이다(= tickets[i][1])
// deps가 들어갈 수록 깊어지므로 현재 count+1을 전달해준다.
// 이때 deps는 결국 tickest에 있는 역들의 총 수와 같다.
// 계속 dfs로 내려갈 수 있다면 결과값 역시 계속 true를 반환할 것이다.
// 만약 false를 반환하면 이 단계를 건너띄고 방문취소 단계로 넘어간다.
if(dfs(tickets[i][1], count+1)) return true;
visited[i] = false; // 현재노드 방문처리 취소
}
}
// 전체를 탐색하지 못한 경우가 발생했으므로
// 지금 들어간 역은 유효 경로가 아니다.
// 따라서 pop()을 통해 제거해주고 다시 이전을 돌아가야한다.
result.pop();
return false;
}위 재귀함수의 작동원리가 잘 이해가 가지 않는다면 직접 간단한 예제를 손으로 그려가며 일일이 내부로직을 살펴보는 것을 추천한다. 재귀로 DFS 를 구현하는 것이 간편하다고 했는데 처음 이와 같은 구조를 보면 뭐가 간편한거지라고 생각할 수 있다. 재귀함수의 쓰임에 익숙해지고 또한 DFS를 재귀로 많이 다루어보면서 나중에 stack으로 DFS를 따로 구현해본다면 왜 간편하다고 말하는지 이해할 수 있을 것이다.
모든 도시를 방문할 수 없는 경우가 주어지지 않는다고 했으므로 우리는 구현한 DFS 함수를 dfs("ICN" , 0) 으로 호출하고 answer를 return 해주면 된다. 이때 count를 0으로 전달하는 이유는, 항상 return값 배열의 개수 = tickets의 길이 + 1 가 되기 때문이다. 왜냐하면 처음 시작역 + 도착역이면서 동시에 출발역 + 도착역이면서 동시에 출발역+ ... + 도착역이면서 동시에 출발역 + 종착역으로 여행경로가 설정되므로 마지막 종착역이 추가 계산되어야 하기 때문이다.
주석을 제외한 전체코드는 다음과 같다.
function solution(tickets) {
let answer = [];
const result = [];
const visited = [];
tickets.sort();
const len = tickets.length;
const dfs = (str, count) => {
result.push(str);
if(count === len) {
answer = result;
return true;
}
for(let i = 0; i < len; i++) {
if(!visited[i] && tickets[i][0] === str) {
visited[i] = true;
if(dfs(tickets[i][1], count+1)) return true;
visited[i] = false;
}
}
result.pop();
return false;
}
dfs("ICN", 0);
return answer;
}출처
