여행경로 [프로그래머스][DFS][String]

 

[광고 누르면 오늘의 행운 상승!!]

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

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

String dfs문제

1. 참고사항

- route 매개변수를 들고다니면서 route를 갱신
- 모든 티켓을 써야하므로 tickets.length만큼 돌면 return;
- ICN부터 시작
- , 으로 스플릿 후 Arrays.sort로 알파벳 순서로 걸러낸다.

2. 구현

- 티켓 배열에서 ICN이 from위치에 있으면 dfs 시작
- route 매개변수를 전달하면서 route 갱신
- 티켓배열에서 end가 from인 배열을 찾아내서 dfs 
- route에 end + ',' 를 더해가면서 전달
- cnt가 tickets.length가 되면 (모든 티켓을 소모하면) return;
- ,으로 스플릿 후 Arrays.sort를 이용하여 정렬
- 반환

import java.util.*;
import java.io.*;


class Solution {
    
    static boolean visit[];
	static List<String> list = new ArrayList<>();
    
    public String[] solution(String[][] tickets) {
       visit = new boolean[tickets.length];
		
		for(int i = 0 ; i < tickets.length; i++) {
			
			String from = tickets[i][0];
			String to = tickets[i][1];
			
			if(from.equals("ICN")) {
				visit[i] = true;
				dfs(tickets, to, 1,from + ",");
				visit[i] = false;
			}
		}
		
		Collections.sort(list);
		String[] answer = list.get(0).split(",");

		return answer;
    }
	
	public static void dfs(String[][] tickets, String end, int cnt, String route) {
		
		if(cnt==tickets.length) {
			list.add(route+end);
			return;
		}
		
		for(int i = 0 ; i < tickets.length ; i++) {
			String from = tickets[i][0];
			String to = tickets[i][1];
			
			if(end.equals(from) && !visit[i]) {
				visit[i] = true;
				dfs(tickets, to, cnt+1,route + end + ",");
				visit[i] = false;
			}
		}
	}
}