[프로그래머스] 여행경로 - JAVA

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/43164

문제 설명

DFS/BFS 공부 중 풀어본 문제다. 이론은 대충 알겠는데 막상 구현하려니 머리가 터질 것 같았다. ㅋㅋㅋ
DFS는 깊이 우선 탐색으로 함수 속에 함수... 그 속에 함수... 또 그 속에 함수... 이런 식으로 동작하게끔 재귀함수를 호출하여 구현하는 것이 대부분이다.
나중에 더 공부하다 이론과 구현이 잘 정립되면 포스팅 해봐야겠다.
이 문제는 DFS를 이용하라고 말해주고 있는 것 같아서 DFS로 풀었다.

문제를 보면 알다시피, 만약 내가 갈 다음 도시가 하나가 아니라 여러 곳으로 배열이 존재한다면, 알파벳 순서가 앞서는 경로를 return하라고 되어있다. 이것을 어떻게 할까 하다 저번에 자동으로 값을 정리해주는 아주 편리한 PriorityQueue가 퍼뜩 생각이 났다.

통과 코드

import java.util.*;

class Solution {
	// 들어온 문자열을 오름차순으로 정렬해주기 위해 PriorityQueue를 만들었다.
    public Queue<String> pq = new PriorityQueue<>();
    // 요건 dfs에서 지나간 배열을 다시 들르게 하지 않기 위한 플래그이다.
    public boolean[] visited;
    
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        // 처음 출발은 무조건 "ICN"공항에서 출발한다기에 그냥 값으로 못박아버렸다.
        dfs(tickets, "ICN", 0, "ICN");
        // PriorityQueue에 들어온 값들 중 처음 값이 최적 경로이므로 첫 값을 배열로 넣었다.
        String[] answer = pq.peek().split(",");
        return answer;
    }
    
    public void dfs(String[][] tickets, String currentCity, int cnt, String path){
    	// 5. count가 tickets.length와 같으면 모든 배열을 순회한 것이므로
        if(cnt == tickets.length){
        	// 6. pq에 전체 여행 경로를 추가
            pq.add(path);
            return;
        }
        for(int i=0;i<tickets.length;i++){
        	// 1. 간 적이 없고 && 현재 도시가 다음 여행 경로의 도착지라면
            if(!visited[i] && currentCity.equals(tickets[i][0])){
            	// 2. 갔다고 체크
                visited[i] = true;
                // 3. 그 다음 경로 탐색
                dfs(tickets, tickets[i][1], cnt+1, path +","+ tickets[i][1]);
                // 4. 모든 배열을 순회했으면, 플래그를 초기화
                visited[i] = false;
            }
        }
    }
}

우선 순위 큐(PriorityQueue) 덕분에 따로 값 정렬을 안해도 돼서 좋았다. 그리고 여행 경로를 어떻게 넣을까하다 '결국 알파벳 우선 순위만 비교하면 되는것 아닌가?' 라는 생각이 들어 여행 경로를 하나의 문자열( ex - "ICN,JFK,HND..." )로 만들어 queue에 추가했다.

최종 코드

import java.util.*;

class Solution {
    public Queue<String> pq = new PriorityQueue<>();
    public boolean[] visited;
    
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        dfs(tickets, "ICN", 0, "ICN");
        String[] answer = pq.peek().split(",");
        return answer;
    }
    
    public void dfs(String[][] tickets, String currentCity, int cnt, String path){
        if(cnt == tickets.length){
            pq.add(path);
            return;
        }
        for(int i=0;i<tickets.length;i++){
            if(!visited[i] && currentCity.equals(tickets[i][0])){
                visited[i] = true;
                dfs(tickets, tickets[i][1], cnt+1, path +","+ tickets[i][1]);
                visited[i] = false;
            }
        }
    }
}

여러 사람들의 코드를 볼 때, 주석이 달려있으면 한 줄, 한 줄 이해하기는 좋지만 전체 코드 흐름이 잘 보이지 않는 것 같아 주석이 없는 코드도 밑에 넣어놨다.

최선의 코드는 아닌 것 같지만... DFS를 연습하는 문제로는 정말 괜찮았다. 이런 방법은 어떻게 이론으로 고안한건지 ㅋㅋ. 어렵지만 더 열심히 공부해야겠다.😆