[프로그래머스/Lv. 3] 여행경로 (JAVA)

🔺 문제

프로그래머스

 

🧩  해결 아이디어

• DFS 

1. DFS를 활용해 모든 경우의 수를 구한다.  

  - DFS 종료 조건 ) 모든 티켓을 다 썼을 때, 도착지 값을 이동 경로 리스트에 저장한다.

  - 반복문 ) 방문한 적 없고, 현재 도시가 다음 여행 경로의 도착지라면 탐색

 

2. 이동 경로 리스트를 오름차순으로 정렬하고, 리스트에서 맨 앞 값 (routeList.get(0))을 가져오면 알파벳 순으로 가장 빠른 경로다.

3. 첫 번째 문자열을 공백을 기준으로 분리하여 배열에 저장하고 출력한다.

 

🔺 코드

import java.util.*;
 
class Solution {
    static String[][] tickets;
    
    static boolean[] visited;
    static List<String> routeList = new ArrayList<>();    // 이동 경로 리스트
    static int cnt = 0;
    
    public String[] solution(String[][] tickets) {
        this.tickets = tickets;
        
        visited = new boolean[tickets.length];        
        
        dfs("ICN", "ICN", 0);   // 현재 도시, 여행 경로, 사용한 티켓 수
        
        Collections.sort(routeList);    // 알파벳 순 경로 가져오기 위한 오름차순 정렬
        
        String[] answer = routeList.get(0).split(" ");
        return answer;
    }
    
    private static void dfs(String now, String route, int depth) {    
        if(depth == tickets.length) {   // 모든 티켓 다 썼을 때, 리스트에 이동 경로 추가하기
            routeList.add(route);
            return;
        }
        
        for(int i = 0 ; i < tickets.length ; i++) {
            if(!visited[i] && now.equals(tickets[i][0])) { // 방문한 적 없고, 현재 도시가 다음 여행 경로의 도착지라면 탐색
                visited[i] = true;
                dfs(tickets[i][1], route + " " + tickets[i][1], depth + 1);
                visited[i] = false;
            }
        }
    }
}

 

---

🔺 다른 풀이들

- Node 클래스를 생성하신 풀이

프로그래머스 - 여행경로(Java)

 

---

💬 느낀 점

플그머스로 dfs bfs 푸는 게 헷갈린당.....ㅠ

담엔 꼭 더 잘 풀어보겠다.

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ DFS 풀이 참고

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

 

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