[lv.3] 여행경로

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

• 문제
  

• 풀이
  1) 모든 경우의 경로를 구해서 알파벳 별로 정렬
  2) 출발은 항상 ICN이기에, DFS의 매개변수에 start를 만들고 여기에 ICN을 넣고 시작한다.
  3) 중복일 경우 항공권 중복이 존재하기에 모든 경로, 즉 인덱스 값으로 중복을 체크한다.
  4) 이후 다음 start로 tickets[i][1], 즉 도착지를 시작으로 설정하여 꼬리물기 형식으로 dfs를 돌린다.

• 소감
  내가 몰랐던 것 : 그래프를 Integer가 아닌 String으로 하는 법
  그래프의 표현이 어렵기도 한거도...있긴한데...개쓰레기 문제....
  아니 항공권 중복은 ㅆㅂㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

• 코드

import java.util.*;

class Solution {
    boolean[] check;
    ArrayList<String> route = new ArrayList<>();
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        check = new boolean[tickets.length];
        dfs("ICN", "ICN", tickets, 0);
        Collections.sort(route);
        answer = route.get(0).split(",");
        return answer;
    }
    public void dfs(String start, String str, String[][] tickets, int depth){
        if(depth == tickets.length){
            route.add(str);
            return;
        }
        for(int i=0; i<tickets.length; i++){
            if(start.equals(tickets[i][0]) && !check[i]){
                check[i] = true;
                dfs(tickets[i][1], str+","+tickets[i][1], tickets, depth+1);
                check[i] = false;
            }
        }
    }
}

• 오답 코드 (1번 런타임 오류)

import java.util.*;

class Solution {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] check;
    static int[][] edge;
    static int n;
    static HashMap<String, Integer> airNum;
    static HashMap<Integer, String> airNum2;
    static ArrayList<String> result = new ArrayList<>();
    public String[] solution(String[][] tickets) {
        airNum = new HashMap<>();
        airNum2 = new HashMap<>();
        HashSet<String> memory = new HashSet<>();
        int num = 0;
        int start = -1;
        n = tickets.length;
        for(int i=0; i<tickets.length; i++){
            if(!memory.contains(tickets[i][0])){
                memory.add(tickets[i][0]);
                if(tickets[i][0].equals("ICN")) start = num;
                airNum2.put(num, tickets[i][0]);
                airNum.put(tickets[i][0], num++);
            }
            if(!memory.contains(tickets[i][1])){
                memory.add(tickets[i][1]);
                if(tickets[i][1].equals("ICN")) start = num;
                airNum2.put(num, tickets[i][1]);
                airNum.put(tickets[i][1], num++);
            }
        }
        check = new boolean[n];
        for(int i=0; i<num; i++){
            graph.add(new ArrayList<>());
        }
        edge = new int[tickets.length][2];
        for(int i=0; i<tickets.length; i++){
            int n1 = airNum.get(tickets[i][0]);
            int n2 = airNum.get(tickets[i][1]);
            edge[i][0] = n1;
            edge[i][1] = n2;
            graph.get(n1).add(n2);
        }
        dfs(start, "ICN,", 0);
        Collections.sort(result);
        String[] answer = result.get(0).split(",");
        return answer;
    }
    public void dfs(int now, String str, int depth){
        //System.out.println(str);
        if(depth == n){
            result.add(str);
            return;
        }
        ArrayList<Integer> nowList = graph.get(now);
        for(int next : nowList){
            int idx = 0;
            for(int i=0; i<edge.length; i++){
                if(edge[i][0]==now && edge[i][1]==next){
                    idx = i;
                }
            }
            if(check[idx]) continue;
            check[idx] = true;
            dfs(next, str+airNum2.get(next)+",", depth+1);
            check[idx] = false;
        }
    }
}