[프로그래머스/JAVA] 고득점Kit > 깊이/너비 우선 탐색 > 여행경로 (by 다알쥐AI)

고득점Kit > 깊이/너비 우선 탐색 > 여행경로

 틱톡라이트 초대링크 https://lite.tiktok.com/t/ZSjqX7SfC/

[기간 한정] 보는 재미로, 버는 재미로! 영상만 봐도, 좋아요만 눌러도, 검색만 해도, 포인트가 차

 
※ 문제풀이 방법은 다양합니다. 참고만 해주세요 ※
[문제설명]

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

 

입출력 예 설명

 

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

 

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

---

[간단설명]
티켓을 모두 사용해서, 모든 도시를 방문할 수 있는 경로를 구하는 문제
 
[접근방법]
1. 모든 경우의 수 DFS 탐색(백트랙킹)
2. 알파벳 순으로 정렬하기
3. String 배열로 리턴하기
 
[주의사항]
1. 백트랙킹 안하면 정답을 찾기 어려움
 
 
[소스공개]

import java.util.*;
class Solution {
    
    // 탐색한 모든 경로를 저장하는 리스트
    private static List<String> list = new ArrayList<>();

    public String[] solution(String[][] tickets) {
        
        // 방문체크 배열
        boolean[] visited = new boolean[tickets.length];
        // DFS 탐색(백트랙킹)
        dfs(tickets,visited,"ICN","ICN",0);
        // 알파벳 오름차순 정렬
        Collections.sort(list);
        // 가장 첫번째 리스트를 배열로 반환
        return list.get(0).split("\\|");
        
    }
    
    // DFS 백트랙킹
    public void dfs(String[][] tickets, boolean[] visited, String routs, String airport,int count){
        // 티켓 사이즈와 경로에 추가한 개수가 같으면
        if(tickets.length==count){ 
            list.add(routs);
            return ;
        }
        
        // 모든 경로를 탐색한다
        // 티켓 사이즈만큼 반복
        for(int i=0;i<tickets.length;i++){
            String deaprt = tickets[i][0]; // 출발지
            String arrive = tickets[i][1]; // 도착지
            if(visited[i]) continue; // 방문했으면 PASS
            if(airport.equals(deaprt)){ //재귀로 넘어온 도착지와 현재 출발지가 같으면
                visited[i]=true; //방문체크
                dfs(tickets,visited,routs+"|"+arrive,arrive,count+1); // DFS탐색
                visited[i]=false; //방문체크해제
            }
            
        }
        return;
    }
    
}

 
[실행결과]