프로그래머스 코딩테스트 연습 - 여행경로 (JAVA)

❓ 문제 - 프로그래머스 코딩테스트 연습 여행경로- JAVA 풀이법

출처

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

프로그래머스

 

 

📝 문제해결법

1. 문제

• tickets의 각 행 [a, b]에서 a공항에서 b공항으로 항공권이 있다는 의미
• ICN 항공에서 출발해서 모든 tickets를 한번씩 쓰며 모든 도시를 방문할 때 방문 순서를 구하여라
• tickets중 출발지점이 같으며 도착지가 다른 여러 항공권이 있을 경우 도착지의 알파벳 순서가 더 빠른 순서를 먼저 들려야 함

 

2. 해결 방법

• DFS 방식으로 모든 도시를 방문할 경우를 탐색한다.
• 처음 출발지점은 ICN이고, dfs내에서 tickets의 출발지가 같고, 아직 방문하지 않은 곳이라면 그 도착지를 방문하며 그곳을 다시 출발지점으로 한다.
• 공항 지점을 들르면서 들른 공항에 대한 정보를 str에 빈칸을 띄운 상태로 저장하고, 만약 모든 공항을 들렀을 경우 list에 넣어준다.
• 마지막에 모든 dfs 탐색이 끝난 후에 Collections으로 list를 정렬하면 ICN을 시작점으로 모든 공항을 가는 경우 중  출발지점이 같으며 도착지가 다른 여러 항공권이 있을 경우 도착지의 알파벳 순서가 더 빠른 순서를 구할 수 있게된다.   

 

3. 느낀점

• 완전탐색이라는 것을 찾고, 출발지점과 도착지점을 분리해서 생각하며 Comparable인터페이스로 정렬을 생각해서 문제가 안 풀렸다. 
• 며칠 끙끙 노력하다가 다른 사람들의 코드를 참조하니, tickets를 출발지, 도착지를 나누어서 구현에 적용하는 것이 아니라 어차피 도착지 기준으로 처리하면 똑같기 떄문에  tickets를 이용해서 dfs에 적용했다.
• 풀이만 보고 생각대로 바로 코드를 짜니 코드도 간결해지고 정렬에 대해 많이 고민한 부분도 쉽게 해결되었다..

 

 

💻 소스코드 (JAVA)

import java.util.*;

class Solution {
    public static int cnt;
    public static ArrayList<String> list = new ArrayList<>();
    public static boolean[] visited;
    public static String[][] ticket;
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];

        ticket = tickets;
        dfs("ICN", "ICN", 0);
        
        Collections.sort(list);
        return list.get(0).split(" ");
    }
    
    
    public static void dfs(String t, String str, int depth){ 
       if(depth == ticket.length){
           list.add(str);
           return;
       }
       for(int i=0;i<ticket.length;i++){
           if(!visited[i] && ticket[i][0].equals(t)){
               visited[i] = true;
               dfs(ticket[i][1], str+" "+ticket[i][1], depth+1);
               visited[i] = false;
           }
       } 
        
    }

}