- 문제설명
- 예시
- 해결과정
첫 번째 풀이
- 인접 리스트 내부에 방문처리를 동시에 할 수 있는 방식으로 만들었다.
- dfs를 돌 때 출발지인 "ICN" 내부의 해시맵의 키값을 모두 꺼내 정렬시키고 안쪽으로 파고들게 만들었다.
- 결과는 절반만 통과.
- 문제에 명시되어 있지는 않지만 히든 조건이 있었다.
- 출발지와 목적지가 동일한 티켓이 여러장 있을 수 있었다.
- 이렇게 되면 해시맵 구조를 사용했기에, 중복 티켓을 처리할 수 없었다.
- 코드를 건드리니 점점 사악해져서 해당 풀이는 올바른 접근이 아니라고 판단했다
실패한 코드
- 실패한 원인을 보면, 중복되는 티켓을 처리할 수 없었다 -> 모든 티켓을 처리할 수 없었다 로 이어진다.
- 따라서 관점을 모든 티켓을 처리하는 방식으로 바꿨다.
- 새로운 DFS에서는 "ICN"을 출발지로 삼는, 모든 가능한 경로를 찾는다.
- 이렇게 모든 경로를 찾다보면, 티켓을 다 사용하지 않았는데 순서가 꼬여 탐색이 끝나는 상황이 생긴다.
- 모든 티켓을 사용한 여행 경로의 결과만 얻기 위해서, 종료 조건을 count가 tickets.length와 같아지는 순간으로 만들었다.
- 이제 모든 티켓을 사용하여 만들 수 있는 경로들을 알게됐다.
티켓을 모두 사용한 모든 경로 확보
- 하지만 아직 문제 조건처럼 알파벳이 빠른 순으로 경로들이 정렬되어있진 않다. --> Collentions.sort() 사용
- 이후 가장 앞에 있는 경로를 뽑아서 반환시키면 된다.
- 솔루션
import java.util.*;
class Solution {
static boolean[] ticketUsed;
static ArrayList<String> result;
static int count;
public String[] solution(String[][] tickets) {
ticketUsed = new boolean[tickets.length];
result = new ArrayList<>();
count = 0;
dfs("ICN", "ICN", tickets, count);
Collections.sort(result);
return result.get(0).split(" ");
}
private static void dfs(String start, String routes, String[][] tickets, int count) {
if(count == tickets.length) {
result.add(routes);
return;
}
for(int i = 0; i < tickets.length; i++) {
if(tickets[i][0].equals(start) && !ticketUsed[i]) {
ticketUsed[i] = true;
count++;
dfs(tickets[i][1], routes + " " + tickets[i][1], tickets, count);
ticketUsed[i] = false;
count--;
}
}
}
}
- 정리
- static 변수를 활용하면 메소드를 생성하기 편리하다.