체감 난이도 = 상
https://school.programmers.co.kr/learn/courses/30/lessons/43164#
문제분석 및 설계
ICN에서 출발하고, 티켓의 정보를 통해 연결되어있는 공항으로 이동할 수 있습니다.
따라서,tickets의 정보를 기반으로 공항 연결정보를 연결리스트 타입의 배열에 담겠습니다.
연결리스트를 dfs로 탐색하면서, 모든 티켓을 다 사용했다면 해당 루트를 결과로 도출합니다.
이때 가능한 경로가 많을경우 알파벳 순서로 앞서는 경로를 return해야하기 때문에, 연결정보를 담은 배열의 각 리스트를 오름차순정렬합니다.
헷갈린 부분
dfs를 호출하기 전에 정답 리스트에 현재 노드를 담고 - dfs를 호출하고 - dfs가 끝나면 정답 리스트에서 현재 노드를 제거하는 방식으로 했다가 많이 꼬였습니다.
이렇게하면 정답 리스트가 계속 갱신되기때문에, dfs호출 전과 후에는 정답리스트가 아닌 방문체크하는 리스트를 조작해주어야합니다.
🤔테스트 케이스 1,2가 틀렸다고 나오며, 문제가 잘 해결되지 않았습니다.
다른사람풀이를 보고 다시 공부했습니다.
해결풀이
다른사람 풀이를 보니, 연결정보를 담은 리스트를 정렬하지 않았습니다. 가능한 모든 경우를 리스트에 담은 후, 마지막에 리스트를 정렬합니다.
그리고 리스트의 가장 첫 원소를 정답으로 return합니다.
코드
import java.util.*;
class Solution {
List<Stack<String>> result;
String[][] tickets;
public String[] solution(String[][] tickets) {
result = new ArrayList<>();
this.tickets = tickets;
boolean[] visited = new boolean[tickets.length];
Stack<String> st = new Stack<>();
st.push("ICN");
dfs(visited, st, 0);
if (result.size() > 1) {
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;
}
});
}
Stack<String> res = result.remove(0);
String[] answer = new String[res.size()];
for (int i = 0; i < answer.length; i++) {
answer[i] = res.get(i);
}
return answer;
}
public void dfs(boolean[] visited, Stack<String> st, int len) {
if (len == tickets.length) {
Stack<String> res = new Stack<>();
for (String s : st) {
res.push(s);
}
result.add(res);
return;
}
String arrive = st.peek();
for (int i = 0; i < tickets.length; i++) {
String[] tic = tickets[i];
if (!visited[i] && arrive.equals(tic[0])) {
st.push(tic[1]);
visited[i] = true;
dfs(visited, st, len + 1);
visited[i] = false;
st.pop();
}
}
}
}공부한 사항
-
List를 배열로 변환 =
toArray()
:String[] arr = arrList.toArray(new String[arrList.size()]); -
Stack은 index가 있다. 맨처음 들어간 값(가장 아래 있는 것)이 0인덱스이다.
-
List<Stack<String>> result처럼 List타입으로 Stack을 지정하는게 가능하다.
<Stack의 메서드>
add(): true를 return /push(): push한 item을 return
->add(index i): index를 주어 특정 위치에 끼워넣는 것이 가능indexOf(변수): 파라미터로 넣은 값의 index 리턴, 없으면 -1 리턴get(index): 파라미터 index에 해당하는 값을 리턴
코드 개선
스택을 사용할 때에 Stack보다 Deque를 사용하는 것을 권장하고있습니다.
따라서, Deque를 사용한 코드로 개선해보겠습니다.
import java.util.*;
class Solution {
List<Deque<String>> result;
String[][] tickets;
public String[] solution(String[][] tickets) {
result = new ArrayList<>();
this.tickets = tickets;
boolean[] visited = new boolean[tickets.length];
Deque<String> dq = new ArrayDeque<>();
dq.push("ICN");
dfs(visited, dq, 0);
if (result.size() > 1) {
Collections.sort(result, new Comparator<Deque<String>>() {
@Override
public int compare(Deque<String> o1, Deque<String> o2) {
Iterator<String> it1 = o1.iterator();
Iterator<String> it2 = o2.iterator();
while (it1.hasNext() && it2.hasNext()) {
String s1 = it1.next();
String s2 = it2.next();
if (!s1.equals(s2)) {
return s1.compareTo(s2);
}
}
return 0;
}
});
}
Deque<String> res = result.remove(0);
String[] answer = new String[res.size()];
int i = 0;
for (String s : res) {
answer[i++] = s;
}
return answer;
}
public void dfs(boolean[] visited, Deque<String> dq, int len) {
if (len == tickets.length) {
Deque<String> res = new ArrayDeque<>(dq);
result.add(res);
return;
}
String arrive = dq.peekLast();
for (int i = 0; i < tickets.length; i++) {
String[] tic = tickets[i];
if (!visited[i] && arrive.equals(tic[0])) {
dq.add(tic[1]);
visited[i] = true;
dfs(visited, dq, len + 1);
visited[i] = false;
dq.removeLast();
}
}
}
}- Deque를 사용할 때 코드에서
dq외 다른 다양한 부분에서는,Deque로 해야할지ArrayDeque로 해야할지 고민이었습니다. 코드를 보면 알 수 있듯, 구현체가 아닌 Deque 인터페이스를 사용합니다.
특히,compare의 파라미터도 Deque타입으로 구현합니다. - Deque를 탐색할 때에는 Iterator를 사용합니다.
