프로그래머스) 332. 여행 경로(자바)

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

문제 : 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 “ICN” 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

https://301choso.github.io/leetcode/%EC%9E%90%EB%B0%94%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-)-%EC%9D%BC%EC%A0%95-%EC%9E%AC%EA%B5%AC%EC%84%B1/
이 문제와 완전 비슷한 문제
풀이를 똑같이 써도 성공한다.

나는 우선순위큐를 사용했는데 다른 사람은 스택으로도 풀었다.
그리고 compare를 이용하여 정렬을 하였다.

import java.util.*;

class Solution {
    List<Stack<String>> result;
    String[][] tickets;

    public String[] solution(String[][] tickets) {
        result = new ArrayList<>();
        this.tickets = tickets;

        boolean[] visited = new boolean[tickets.length];
        Stack<String> st = new Stack<>();
        st.push("ICN");

        dfs(visited, st, 0);

        if (result.size() > 1) {
            Collections.sort(result, new Comparator<Stack<String>>() {
                @Override
                public int compare(Stack<String> o1, Stack<String> o2) {
                    for (int i = 0; i < o1.size(); i++) {
                        String s1 = o1.get(i);
                        String s2 = o2.get(i);

                        if (!s1.equals(s2)) {
                            return s1.compareTo(s2);
                        }
                    }

                    return 0;
                }
            });
        }

        Stack<String> res = result.remove(0);
        String[] answer = new String[res.size()];

        for (int i = 0; i < answer.length; i++) {
            answer[i] = res.get(i);
        }

        return answer;
    }

    public void dfs(boolean[] visited, Stack<String> st, int len) {
        if (len == tickets.length) {
            Stack<String> res = new Stack<>();
            for (String s : st) {
                res.push(s);
            }
            result.add(res);
            return;
        }

        String arrive = st.peek();

        for (int i = 0; i < tickets.length; i++) {
            String[] tic = tickets[i];

            if (!visited[i] && arrive.equals(tic[0])) {
                st.push(tic[1]);
                visited[i] = true;
                dfs(visited, st, len + 1);
                visited[i] = false;
                st.pop();
            }
        }
    }
}

import java.util.ArrayList;
import java.util.Collections;
class Solution {
    static boolean[] visit;
    static ArrayList<String> list=new ArrayList<>();

    public String[] solution(String[][] tickets) {
        visit = new boolean[tickets.length];
        DFS(0, "ICN", "ICN", tickets);
        Collections.sort(list);
        String[] temp = list.get(0).split(" ");
        return temp;
    }

    private static void DFS(int cnt, String icn, String word, String[][] tickets) {
        if (cnt == tickets.length) {
            list.add(word);
        }else{
            for (int i = 0; i < tickets.length; i++) {
                if (!visit[i] && tickets[i][0].equals(icn)) { // 방문한적 없고, 출발지가 맞으면
                    visit[i]=true;
                    DFS(cnt+1, tickets[i][1], word+" "+tickets[i][1] ,tickets); // word에 다 붙임
                    visit[i]=false;
                }
            }
        }
    }
}

cnt와 ticket.length가 같으면 결과값 list에 담고 dfs를 다녀와서 마지막에 정렬을 해준 후 붙여 놓았던 것을 떼서 반환

• 방문여부를 visited[i] = true > dfs 재귀호출 > visited[i] = false로 바꿔주는 이유 나에 연결된 경로가 두개 있을 때 하나 재귀로 탐색 완료 후, 다음 경로 가기 위해 다시 나부터 시작해야 하므로, 다음 i로 넘어가기 전에 현재 i의 방문여부를 false로 바꿔주는 것

• 정렬방법

  1. compare구현
  2. Collections.sort()