[프로그래머스][Level3][Java] 여행경로

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

코딩테스트 연습 - 여행경로

문제풀이

우선 출발지가 "ICN" 인 것들을 찾아야 하기 때문에 따로 반복문으로 찾아야한다.

이후 주어진 항공권을 모두 사용해야 되기때문에 완전탐색을 위한 DFS을 해줘야한다.

파라미터로 도착지만 입력받아, 아직 경유하지 않고 도착지와 같은 시작지점을 찾는다.

깊이는 티켓길이 +1만큼이 경로길이 이다. 조건에 만족 한다면 알파벳 순서에 따라 결과값을 갱신해줘야한다.

본인의 코드 같은 경우는 결과값을 다 저장해서 정렬해줘도 되지만, 매번 저장된 결과값과 일일히 비교해서

알파벳이 빠른 순서를 결과값으로 갱신해주었다.

 

코드

import java.util.*;

class Solution {
    static int N;
    static boolean[] visited;
    static String[] tempWay;
    static String[] pathWay;
    
    public String[] solution(String[][] tickets) {
        N = tickets.length;
        pathWay = new String[N+1];
        
        // 출발지 선택
        for(int i=0; i<N; i++){
        	if(tickets[i][0].equals("ICN") == false) continue;
            visited = new boolean[N];
            visited[i] = true;
            tempWay = new String[N+1];
            tempWay[0] = tickets[i][0];
            dfs(1, tickets[i][1], tickets);
        }
        
        return pathWay;
    }
    
    public void dfs(int cnt, String end, String[][] tickets){
        if( cnt == N){
            tempWay[cnt] = end;
            
            //경로 저장이 처음일때
            if(pathWay[0] == null) {
            	pathWay = Arrays.copyOf(tempWay, tempWay.length);
            	return;
            }
            
            //비교, 알파벳 앞설때 교체
            for(int i =0; i<tempWay.length; i++) {
            	if(pathWay[i].compareTo(tempWay[i]) > 0) {
            		pathWay = Arrays.copyOf(tempWay, tempWay.length);
            		break;
            	}
            	else if(pathWay[i].compareTo(tempWay[i]) < 0) break;
            }
            
            return;
        }
        
        // 경유지 확인
        for(int i=0; i<N; i++){
            if(visited[i] == true || end.equals(tickets[i][0]) == false) continue;
            
            visited[i] = true;
            tempWay[cnt] = tickets[i][0];
            dfs(cnt+1, tickets[i][1], tickets);
            visited[i] = false;
        }
    }
}