[JAVA/프로그래머스] 깊이/너비 우선 탐색(DFS/BFS): 여행경로

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
class Solution {
    int n; // 티켓 수
    boolean[] visit;
    ArrayList<String> list; // 최종 경로 저장
    String[][] map; // 티켓 참조 변수
    
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        
        n=tickets.length;
        visit=new boolean[n];
        list=new ArrayList<>();
        map=tickets;
        
        for(int i=0;i<n;i++){
            if(tickets[i][0].equals("ICN")){ // 시작
                visit[i]=true; // 티켓 사용
                dfs(tickets[i][1], 1, new StringBuilder("ICN "));
                visit[i]=false; // 사용 안 할 경우
            }
        }
        
        Collections.sort(list); // 알파벳기준 오름차순 정렬
        return list.get(0).split(" "); // 첫번째 값 리턴
    }
    
    public void dfs(String dept, int idx, StringBuilder sb){
        sb.append(dept+" "); // 방문
        if(idx==n){ // 경로 생성 완료
            list.add(sb.toString());
            return;
        }
        
        for(int i=0;i<n;i++){ // 티켓들 체크
            if(map[i][0].equals(dept) && !visit[i]){ // 다음 티켓 찾음
                visit[i]=true; // 티켓 사용
                dfs(map[i][1], idx+1, sb);
                visit[i]=false; // 사용 안 할 경우
                sb.delete(sb.length()-4, sb.length());
            }
        }
    }
}