프로그래머스 고득점 kit DFS/BFS 분류의 마지막 문제 ! level 3인 여행 경로 문제를 풀었습니다.
이렇게 DFS/BFS 분류도 끝 ! ✅ (문제링크)
level3인 만큼 마냥 쉬운 문제는 아니지만, 그리 어려운 문제는 아니었는데 한참 시간을 잡아먹은 문제입니다. 너무너무 답답해서 도움을 요청하는 글까지 써서 SNS에 공유까지 했으니까요..! 물론 글을 읽고 관심 가져주신 많은 지인분들 덕분에 해결했습니다 ! 제가 고충을 겪은 부분은 이 시리즈의 바로 이전글 혹은 여기를 클릭하여 확인하실 수 있습니다 !
물론 아래에 적는 풀이 방법에서도 간단하게 문제를 언급하고 그리고 지인 덕분에 발견한 문제와 그 해결방안을 언급할 것입니다 !
문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "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"] |
풀이 방법
처음에는 문제를 보고, 각 나라를 노드로 두고 연결 그래프를 구성해야 한다고 생각하였습니다. 출발지 나라 이름을 키 값으로 두고 도착지가 저장된 PriorityQueue를 밸류로 하는 자료구조로 그래프를 구성하여 문제를 풀었습니다. 하지만 시간초과가 발생하였습니다. 😱 문제를 깨닫고, 그래프를 다시 구성하고 계속해서 그 상태를 갱신하는 과정을 제거해야겠다고 생각하였습니다.
그래서 주어진 tickets 배열 자체를 그래프로 활용할 수 있도록 새로 코드를 작성하였습니다. 티켓 자체를 노드라고 생각하고 탐색하며 다음 노드를 선정해 나가는 방법을 택하였습니다. 이 때, 특정 경로의 탐색은 모든 티켓을 다 사용할 수 없는 경우가 발생하기 때문에 DFS를 활용하여 가장 먼저 모든 티켓을 다 사용하는 경로를 찾아내고자 하였습니다.
이 때, 또 다른 조건이 있는데 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 반환해야 합니다. 이를 효과적으로 구현하기 위해서 모든 경로를 다 찾고 정렬하여 알파벳 순서가 앞서는 경로를 찾는 것이 아니라 알파벳 순서로 탐색을 하면서 가장 먼저 발견하는 경로를 반환하는 방법을 택했습니다. 그것이 시간복잡도 측면에서 더 효율적일 것이라고 생각했기 때문입니다.
알파벳 순서로 탐색을 진행하기 위해서 tickets를 도착지 기준으로 정렬해둔 후 탐색을 시작하였습니다. 시작 도시는 ICN으로 고정되어 있기 때문에 ICN이 출발지이며, 도착지가 알파벳순으로 가장 빠른 티켓이 첫 노드가 될 것입니다. 그렇다면 두 번째 티켓의 출발지가 정해지게 되고, 역시 같은 방법으로 도착지를 정할 수 있기 때문입니다.
위의 방법으로 탐색해 나가면서 모든 노드를 방문하지 않는 경로에 대해서는 결과로 판단하지 않고 계속 탐색을 진행하면 되는 것입니다. DFS를 이용하였기 때문에 물론 visited배열로 각 티켓의 사용 여부를 체크해주었습니다 !
( 사실 설명은 시리즈의 바로 이전글인 HELP ME 글이 더 잘 한 것 같기도..ㅎㅎ.. 잘 이해가 안 가신다면 여기를 클릭하여 한 번 읽어보세요! )
문제와 그 해결 방안
아래의 코드에서 확인하실 수 있겠지만, visited배열로 방문 여부를 체크하는데, C++로 문제를 풀 때는 Call by value와 Call by reference로 재귀를 빠져나오면 그 이전의 visited를 사용할 수 있었지만, 자바에서는 재귀를 빠져나오면 재귀에서 체크된 방문 여부를 다시 해제해 주어야 했습니다. 이 과정에서 아래와 같이 i번째 티켓을 해제해 주어야 하는데, 내가 헷갈려서 start번째의 티켓을 해제해 버린 것이다.. 대체 수십번 디버깅을 하고, 블로그 쓴다고 주석도 달아서 방금 재귀를 빠져나오면서 그 티켓의 사용을 해제한다고 해놓고서 왜 .. 왜.. 저렇게 작성하고.. 몰랐을까.. 멍총.. 그래도 결과적으로 좋은 방법으로 문제를 해결한 것 같아서 좋다 !
[원래 코드]
visited[start] = false[수정 후 코드]
visited[i] = false코드
import java.util.*;
class Solution {
public static String[] answer;
public static boolean[] visited;
public static boolean flag = false;
public static void dfs(String[][] tickets, int start, int count){
visited[start] = true;
answer[count] = tickets[start][0];
if(count == tickets.length-1){
answer[count+1] = tickets[start][1];
flag = true;
return;
}
for(int i=0; i<tickets.length; i++){
if(tickets[i][0].equals(tickets[start][1]) && !visited[i]){
dfs(tickets, i, count+1);
if(flag) return;
visited[i] = false;
}
}
}
public static String[] solution(String[][] tickets) {
answer = new String[tickets.length+1];
visited = new boolean[tickets.length];
Arrays.sort(tickets, new Comparator<String[]>() {
@Override
public int compare(String[] o1, String[] o2) {
return o1[1].compareTo(o2[1]);
}
});
for(int i=0; i<tickets.length; i++){
if(tickets[i][0].equals("ICN")){
Arrays.fill(visited, false);
dfs(tickets, i, 0);
if(flag) break;
}
}
return answer;
}
}