[Programmers] 여행 경로 - Java

Level 3

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

 

문제 풀이

BFS도 나올 줄 알았는데.. 이것도 DFS ㅎ

이번 문제는 시작 지점이 인천으로 고정되어 있기 때문에 그 부분을 주의해서 초기 값을 넣어주고 마찬가지로 재귀함수를 돌려주면 된다. 티켓의 사용여부를 표시하기 위해 visited 리스트를 만들어주고 count 변수로 사용한 티켓 수를 확인할 수 있도록 해줬다.

 

route를 저장하고 정렬하는 부분에서 헤매서 구글링을 했는데 정말,, 아직 난 갈길이 멀다. 문자열로 이어 붙인 다음 리스트에 추가하고 Collections.sort()를 이용해 정렬해서 맨 앞의 요소를 가져온다.  가져온 경로를 split으로 쪼개서 반환하면 끝!

방법은 이 블로그를 참고했다.

 

 

코드

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

class Solution {
    ArrayList<String> allRoute; 
	boolean[] visited;
	
	public void dfs(String start, String[][] tickets, boolean[] visited, String route, int count) {
		// 모든 티켓을 사용한 경우
		if (count == tickets.length) {
			allRoute.add(route);
			return;
		}
		
		for (int i=0; i<tickets.length; i++) {
        	if (!visited[i] && tickets[i][0].equals(start)) {
	        	visited[i] = true;
	        	dfs(tickets[i][1], tickets, visited, route + " " + tickets[i][1], count + 1);
	        	visited[i] = false;
	        	}
        }
	}
	
	public String[] solution(String[][] tickets) {
		String[] answer = {};
        visited = new boolean[tickets.length]; // 티켓 사용 여부
        allRoute = new ArrayList<String>();
        int count = 0;
        
        // 시작지점은 무조건 인천
        dfs("ICN", tickets, visited, "ICN", count);
        Collections.sort(allRoute);
        answer = allRoute.get(0).split(" ");
        
        return answer;
    }
}