[JAVA]43164 여행경로 , DFS

 📚 문제  

프로그래머스

🔍 아이디어  

처음에는 해시맵과 dfs 방법을 이용하여 각 도시에 연결된 다음 코스를 넣고 dfs로 탐색하면서 각 경로에서 갈 수 있는 다음도시를 모두 방문하는 방식으로 진행하였습니다. 이후에 depth 가 티켓의 수만큼 된다면 모든 티켓을 사용한 것이므로 가능 경로여서 리턴하도록 하였습니다.

 

📝 풀이 

import java.util.*;

class FindPath43164 {
    public static final String ICN = "ICN";
    HashMap<String, Integer> hash = new HashMap<>();
    List<List<String>> graph = new LinkedList<>();
    List<String> ans = new ArrayList<>();
    boolean flag = false;

    public String[] solution(String[][] tickets) {
        graph.add(new ArrayList<>());
        for (String[] ticket : tickets) {

            for (int j = 0; j < 2; j++) {
                if (!hash.containsKey(ticket[j])) {
                    hash.put(ticket[j], hash.size());
                    graph.add(new ArrayList<>());
                }
            }
            int start = hash.get(ticket[0]);
            graph.get(start).add(ticket[1]);
        }

        ans.add(ICN); //시작
        dfs(hash.get(ICN),1,tickets.length+1);

        return ans.toArray(String[]::new);
    }


    public void dfs(int now, int depth, int goalDepth) {
        if (depth == goalDepth) {
            flag = true;
            return;
        }
        if (checkVisited()) return;

        if (graph.get(now).size() == 0) return;
        Collections.sort(graph.get(now));

        int size = graph.get(now).size();
        for (int i = 0; i < size; i++) {
            String nextCity = graph.get(now).remove(i);
            ans.add(nextCity);

            dfs(hash.get(nextCity),depth+1,goalDepth);
            if (flag) return;

            ans.remove(ans.lastIndexOf(nextCity));
            graph.get(now).add(i, nextCity);
        }
    }

    private boolean checkVisited() {
        for (List<String> strings : graph) {
            if (strings.size() != 0) return false;
        }
        return true;
    }


    public static void main(String[] args) {
        FindPath43164 solution = new FindPath43164();
//        System.out.println(Arrays.toString(solution.solution(new String[][]{{"ICN", "JFK"}, {"HND", "IAD"}, {"JFK", "HND"}})));
//        System.out.println(Arrays.toString(solution.solution(new String[][]{{"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL", "SFO"}})));
        System.out.println(Arrays.toString(solution.solution(new String[][]{{"ICN", "BOO"}, {"ICN", "COO"}, {"COO", "DOO"}, {"DOO", "COO"}, {"BOO", "DOO"}, {"DOO", "BOO"}, {"BOO", "ICN"}, {"COO", "BOO"}}
        )));
    }
}

 

 

🔍 아이디어  

하지만 더 간단한 풀이방법은 없을까 고민하다가 그냥 각 티켓에 대해서 확인하는 방식으로 진행하였습니다

처음 시작은 인천에서 시작하여 인천에서 출발하고 아직 사용하지 않은티겟을 array에 넣고 알파벳 순 정렬합니다.

이후에 가능한 경로를 앞에서 부터 ans배열에 넣고, visit처리 후에 다음경로에 대한 탐색을 진행합니다(dfs)

그렇게 티켓의 개수와 dfs의 탐색 깊이가 같으면 모두 탐색한것이므로 탐색을 종료하고 리턴하도록 하였습니다.

 

📝 풀이 

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

class Solution {
    public static final String ICN = "ICN";
    private String[][] tickets;
    private boolean[] visited;
    private String[] ans ;
    private boolean flag = false;

    public String[] solution(String[][] tickets) {
        this.tickets = tickets;
        visited = new boolean[tickets.length];
        ans = new String[tickets.length + 1];
        ans[0] = ICN;
        dfs(ICN, 0);

        return ans;
    }

    public void dfs(String now, int depth) {
        if (depth == tickets.length) {
            flag = true;
        }else{
            List<Integer> able = new ArrayList<>();
            for (int i = 0; i < tickets.length; i++) {
                if (tickets[i][0].equals(now) && !visited[i]) {
                    able.add(i);
                }
            }

            Collections.sort(able, (o1, o2) -> tickets[o1][1].compareTo(tickets[o2][1]));

            for (int ableIndex : able) {
                String next = tickets[ableIndex][1];
                ans[depth + 1] = next;
                visited[ableIndex] = true;
                
                dfs(next, depth + 1);
                if (flag) return; //이미 찾음
                visited[ableIndex] = false;
            }
        }
    }

}