주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
- DFS 사용해 풀도록 하자.
평범한 DFS 문제이다.
결과를 저장할 때는 사전적으로 우선순위에 있는 것을 저장해주면 된다.
큰 어려움은 없다.
다만 표본이 10,000까지 될 수 있는 만큼 python에서 푼다면 depth이슈를 조심하도록 하자.
# python
import sys
sys.setrecursionlimit(100001)
answer = []
def search(depth,dic,now,stack):
if len(stack) == depth:
answer.append(stack.copy())
return
elif now in dic:
for i in range(len(dic[now])):
if dic[now][i] != "-":
temp = dic[now][i]
dic[now][i] = "-"
stack.append(temp)
search(depth,dic,temp,stack)
dic[now][i] = temp
stack.pop()
def solution(tickets):
dic = dict()
for i in tickets:
start,end = i
if start not in dic:
dic[start] = []
dic[start].append(end)
search(len(tickets)+1,dic,"ICN",["ICN"])
return sorted(answer)[0]
//java
import java.util.*;
class Solution {
ArrayList<String> answer = new ArrayList<>();
public void set_answer(ArrayList<String> stack){
for(int i=0;i<stack.size();i++)
answer.set(i,stack.get(i));
}
public void search(int depth, HashMap<String,ArrayList<String>> dic, String now, ArrayList<String> stack){
if (stack.size() == depth){
if(answer.size() != 0){
for(int i=0;i<depth;i++)
if(stack.get(i).compareTo(answer.get(i)) < 0)
set_answer(stack);
else if(stack.get(i).compareTo(answer.get(i)) > 0)
break;
}else
for(String s : stack)
answer.add(s);
return;
}
else if (dic.get(now) != null){
for(int i=0;i<dic.get(now).size();i++){
if(dic.get(now).get(i) != "-"){
String temp = dic.get(now).get(i);
dic.get(now).set(i,"-");
stack.add(temp);
search(depth,dic,temp,stack);
stack.remove(stack.size()-1);
dic.get(now).set(i,temp);
}
}
}
}
public String[] solution(String[][] tickets) {
ArrayList<String> stack = new ArrayList<>();
HashMap<String,ArrayList<String>> dic = new HashMap<>();
for (String[] ticket : tickets){
if(dic.get(ticket[0]) == null){
ArrayList<String> end = new ArrayList<>();
dic.put(ticket[0],end);
}
dic.get(ticket[0]).add(ticket[1]);
}
stack.add("ICN");
search(tickets.length+1,dic,"ICN",stack);
String[] result = new String[tickets.length+1];
for(int i=0;i<tickets.length+1;i++)
result[i] = answer.get(i);
return result;
}
}
요즘 Python 이외에 Java로도 알고리즘 문제를 푸는 것을 연습하고 있다.
Python에서 되던게 안되고, 복잡하고, 에러나고 아주 골치가 아프다.. Python은 위대해!
하지만, 반드시 필요하다고 생각하고, 앞으로도 알고리즘 문제를 풀 때는
두 언어로 모두 풀어볼 생각이다.
제일 골치아픈 부분은 Python에서는 list하나로 모든 것을 해결할 수 있는 반면,
Java의 경우에는 많은 것이 세분화 되어있고, 규칙이 까다롭다보니 연습이 많이 필요할 거 같다.