[Programmers] #43164 - 여행경로 [Java][C++][Python]
[Programmers] #43164 - 여행경로 [Java][C++][Python]
1. 아이디어
항공권을 모두 한 번씩 써서 ICN에서 출발하는 경로를 만들되, 가능한 경로가 여러 개면 알파벳순으로 가장 앞선 경로를 구하는 문제다. 공항 이름은 모두 대문자 3글자라 경로의 알파벳순 비교는 앞에서부터 한 공항씩 비교한 결과이므로, 각 공항에서 도착지가 알파벳순으로 앞선 항공권부터 써 가며 깊이 우선으로 경로를 늘리면 탐색이 경로를 알파벳순으로 차례차례 만들어 보게 되고, 모든 항공권을 쓴 경로가 처음 완성되는 순간 그 경로가 답이다. 항공권을 도착지 기준으로 한 번 정렬해 두면 출발지가 현재 공항인 항공권만 골라 쓰는 반복에서 같은 출발지의 항공권은 자연히 도착지순으로 나온다.
다만 도착지가 가장 앞선 항공권이 항상 답으로 이어지지는 않는다. 도착한 공항에서 나갈 항공권이 없는데 쓰지 않은 항공권이 남아 있으면 막다른 길이므로, 마지막으로 쓴 항공권을 되돌리고 다음 도착지를 시도하는 백트래킹이 필요하다. 같은 공항을 여러 번 지날 수 있어서 공항이 아니라 항공권마다 사용 여부를 기록한다.
2. 코드
풀이 [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;
class Solution {
static boolean[] vis;
static List<String> ans = new ArrayList<>();
public String[] solution(String[][] tickets) {
Arrays.sort(tickets, (o1, o2) -> o1[1].compareTo(o2[1]));
vis = new boolean[tickets.length];
ans.add("ICN");
dfs("ICN", 0, tickets);
return ans.toArray(new String[0]);
}
static boolean dfs(String cur, int depth, String[][] tickets) {
if (depth == tickets.length) return true;
for (int i = 0; i < tickets.length; i++) {
if (vis[i]) continue;
if (!tickets[i][0].equals(cur)) continue;
ans.add(tickets[i][1]);
vis[i] = true;
if (dfs(tickets[i][1], depth + 1, tickets)) return true;
ans.removeLast();
vis[i] = false;
}
return false;
}
}
removeLast는 Java 21부터 쓸 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 10000;
bool vis[MAX_N];
vector<string> ans;
bool dfs(string& cur, int depth, vector<vector<string>>& tickets) {
if (depth == tickets.size()) return true;
for (int i = 0; i < tickets.size(); i++) {
if (vis[i]) continue;
if (tickets[i][0] != cur) continue;
ans.push_back(tickets[i][1]);
vis[i] = true;
if (dfs(tickets[i][1], depth + 1, tickets)) return true;
ans.pop_back();
vis[i] = false;
}
return false;
}
vector<string> solution(vector<vector<string>> tickets) {
sort(tickets.begin(), tickets.end(), [](auto& a, auto& b) {
return a[1] < b[1];
});
string start = "ICN";
ans.push_back(start);
dfs(start, 0, tickets);
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import sys
sys.setrecursionlimit(10**6)
def solution(tickets):
tickets.sort(key=lambda t: t[1])
vis = [False] * len(tickets)
ans = ["ICN"]
def dfs(cur, depth):
if depth == len(tickets):
return True
for i in range(len(tickets)):
if vis[i]:
continue
if tickets[i][0] != cur:
continue
ans.append(tickets[i][1])
vis[i] = True
if dfs(tickets[i][1], depth + 1):
return True
ans.pop()
vis[i] = False
return False
dfs("ICN", 0)
return ans
재귀 깊이가 항공권 수만큼 깊어져 기본 한도에 걸릴 수 있어 sys.setrecursionlimit으로 한도를 올렸다.
This post is licensed under CC BY 4.0 by the author.