[프로그래머스] 여행경로 / java

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

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

 

[ 코드 ]

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    List<String> list = new ArrayList<>();
    static String route = "";
    static boolean[] visit;
	
	private void dfs(String[][] tickets, String end, int cnt) {
		route += end + ",";
		
		if(cnt == tickets.length) {
			list.add(route); return;
		}
		
		for(int i = 0; i < tickets.length; i++) {
			String s = tickets[i][0], e = tickets[i][1];
			if(s.equals(end) && !visit[i]) {
				visit[i] = true;
				dfs(tickets, e, cnt + 1);
				visit[i] = false; route = route.substring(0, route.length()-4);
			}
		}
	}
	
	public String[] solution(String[][] tickets) {
		for(int i = 0; i < tickets.length; i++) {
			visit = new boolean[tickets.length];
			String start = tickets[i][0], end = tickets[i][1];
			
			if(start.equals("ICN")) {
				route = start + ","; visit[i] = true; 
				dfs(tickets, end, 1);
			}
		}
		
		Collections.sort(list);
		String[] answer = list.get(0).split(",");

		return answer;
	}
}

 

출처 : https://geehye.github.io/programmers-dfs-bfs-04/#

 

 

 

 

 

[ 틀린 코드 ] 

 

import java.util.*;

class Solution {
    static String[] answer, ans;
    static int trip = 0;
    static boolean[] visited;
    
    public String[] solution(String[][] tickets) {
        answer = new String[tickets.length+1];
        ans = new String[tickets.length+1];
        
        visited = new boolean[tickets.length];
        
        for(int i=0; i<tickets.length; i++){
            if(tickets[i][0].equals("ICN")){
                ans[0] = "ICN";
                visited[i] = true;
                dfs(1, i, tickets.length, tickets);
                visited = new boolean[tickets.length];
                ans = new String[tickets.length+1];
            }
        }
        
        return answer;
    }
    
    public static void dfs(int travel, int r, int length, String[][] tickets){
        if(travel==length){
            ans[travel] = tickets[r][1];
            trip++;
            check();
            return;
        }
        
        for(int i=0; i<length; i++){
            if(!visited[i] && tickets[i][0].equals(tickets[r][1])){ // 새 티켓의 출발지 = 이전 티켓의 도착지
                ans[travel] = tickets[r][1];
                visited[i] = true;
                dfs(travel+1, i, length, tickets);
            }
        }
    }
    
    public static void check(){
        String line1 = "";
        String line2 = "";
        String arr[] = new String[2];
        
        if(trip==1) {
        	for(int i=0; i<ans.length; i++) {
        		answer[i] = ans[i];
        	}
        	return;
        }else {
            for(int i=0; i<answer.length; i++){
                line1 += ans[i];
                line2 += answer[i];
            }
            
            arr[0] = line1;
            arr[1] = line2;
            
            Arrays.sort(arr);
            
            if(arr[0].equals(line1)) {
            	for(int i=0; i<ans.length; i++) {
            		answer[i] = ans[i];
            	}
            }
        }
    }
}

 

 

틀린 코드에서는 check 부분을 답이 하나가 생길 때마다 비교하여 저장하는 방식으로 하였는데

answer 부분에서 잘못 저장되는 오류도 있었고,

그보다 ArrayList에 다 넣어서 Collections.sort로 해결하는 것이 더 빨랐다.

 

그리고 답을 저장할 때 ","를 넣어 저장하여 추후에 split을 할 때 유용하도록 했다.

 

 

 

 

※ 오늘의 교훈

더 쉬운 방법이 생기면 그걸로 가보는 것도 나쁘지 않다.