[프로그래머스(programmers)] (Lv3) 여행경로

알고리즘 문제 풀이 / 프로그래머스 (programmers)  -  여행경로

 

문제 링크

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

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

 

 

문제 풀이

 

이 코드는 유일하게 아직 미완성인 상태다. 실행시켜보면 문제 5,6개 정도 런타임에러가 난다.

모든 경우 다 맞다고 생각했는데 오류가나서 생각해보니, 시작지점이 같을 때, 도착 지점이 알파벳 순서가 빠르다고 무조건 그게 1순위가 아니였다. 그 도착지점으로 갔을 때 다시 시작지점으로 갈 수 있는 경로가 있을 때에만 알파벳 순서가 허용되는 것이었다. 안그러면 경로를 마칠 수 없다. 이 문제는 그래프를 사용해야할 것 같은데 그 알고리즘을 아직 공부를 못해서 공부마치면 다시 수정하겠다.

public static String[] solution(String[][] tickets) {
	List<String> list = new ArrayList<>();
	String first = "ICN";
	boolean check[] = new boolean[tickets.length+1];
	int min_i = 0;
	int count = 0;
    
	while ( count < tickets.length) {
		list.add(first);
			
		min_i = -1;
		String min_t = "";
			
		for(int i = 0; i < tickets.length; i++) {
			if( !check[i] && tickets[i][0].equals(first)) {
				if(min_i != -1 && min_t.compareTo(tickets[i][1]) < 0) {
					continue;
				}
				min_i = i;
				min_t = tickets[i][1];
			}
		}
			
		first = min_t;
		check[min_i] = true;
		count++;
		
	}
	list.add(tickets[min_i][1]);
        
	String[] answer = list.toArray(new String[list.size()]);

	return answer;
}