프로그래머스 | 여행 경로 - java

프로그래머스

 

 

# 내가 처음으로 통과한 코드

import java.util.*;

class Solution {

    private static class Edge {
        public int to;
        public int gain;

        public Edge(int to, int gain) {
            this.to = to;
            this.gain = gain;
        }
    }

    Map<String, Integer> airportsToIdxMap = new HashMap<>();
    Map<Integer, String> idxToAirportsMap = new HashMap<>();
    List<List<Edge>> adjList = new LinkedList<>();

    String[] ans;
    int[] arr;

    public String[] solution(String[][] tickets) {

        airportsToIdxMap.put("ICN", 0);
        idxToAirportsMap.put(0, "ICN");
        adjList.add(new LinkedList<>());

        int idx = 1;
        for (String[] ticket : tickets) {
            // 고유 공항 추가
            if (!airportsToIdxMap.containsKey(ticket[0])) {
                airportsToIdxMap.put(ticket[0], idx);
                idxToAirportsMap.put(idx++, ticket[0]);
                adjList.add(new LinkedList<>());
            }
            if (!airportsToIdxMap.containsKey(ticket[1])) {
                airportsToIdxMap.put(ticket[1], idx);
                idxToAirportsMap.put(idx++, ticket[1]);
                adjList.add(new LinkedList<>());
            }

            // 연결 리스트 추가
            List<Edge> dept = adjList.get(airportsToIdxMap.get(ticket[0]));
            boolean hasEdge = false;
            for (Edge edge : dept) {
                if (edge.to == airportsToIdxMap.get(ticket[1])) {
                    edge.gain++;
                    break;
                }
            }
            if (!hasEdge) {
                dept.add(new Edge(airportsToIdxMap.get(ticket[1]), 1));
            }
        }
        arr = new int[tickets.length + 1];
        arr[0] = 0;
        dfs(1, 0);

        return ans;
    }

    public void dfs(int depth, int v) {
        // 모든 티켓을 다 사용했으면
        if (depth == arr.length) {
            compareTwoArr();
            return;
        }

        List<Edge> edges = adjList.get(v);
        for (Edge edge : edges) {
            if (edge.gain > 0) {
                edge.gain -= 1;
                arr[depth] = edge.to;
                dfs(depth + 1, edge.to);
                edge.gain += 1;
            }
        }
    }

    // 우선순위 비교
    private void compareTwoArr() {
        if (ans == null) {
            ans = new String[arr.length];
            for (int i = 0; i < ans.length; i++) {
                ans[i] = idxToAirportsMap.get(arr[i]);
            }
            System.out.println(Arrays.toString(ans));
            return;
        }
        String[] convArr = new String[arr.length];
        for (int i = 0; i < convArr.length; i++) {
            convArr[i] = idxToAirportsMap.get(arr[i]);
        }
        System.out.println(Arrays.toString(convArr));
        for (int i = 0; i < convArr.length; i++) {
            if (convArr[i].compareTo(ans[i]) == 0) continue;
            else if (convArr[i].compareTo(ans[i]) > 0) {
                ans = convArr.clone();
                return;
            } else {
                return;
            }
        }
    }
}

 

 

- 풀긴 풀었으나 일단 너무 길고 쓸데없이 복잡해졌다. 사실 패스 된것도 신기할 따름이다

- DFS로 풀어보겠다는 생각에 티켓마다 있는 고유의 공항을 따로 Map으로 저장해놓고 연결리스트를 이용해서 그래프 탐색을 하려고 하는 고정관념에 사로잡혀 있었다.

 

다른 사람들의 코드를 보니 내가 얼마나 뻘짓하고 있었는지 다시금 느끼게 되었다. 잘 짜여진 코드를 배우고 내것으로 만드는 것도 참 중요하다고 느낀다

 

# 다른 사람들의 코드

import java.util.*;

class Solution {

    List<String> pathList = new ArrayList<>();
    boolean[] visited;

    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        dfs(tickets, "ICN", 0, "ICN");
        Collections.sort(pathList);

        return pathList.get(0).split(" ");
    }

    private void dfs(String[][] tickets, String currentCity, int cnt, String path) {
        if(cnt == tickets.length) {
            pathList.add(path);
            return;
        }

        for(int i = 0; i < tickets.length; i++) {
            if(!visited[i] && currentCity.equals(tickets[i][0])) {
                visited[i] = true;
                dfs(tickets, tickets[i][1], cnt + 1, path + " " + tickets[i][1]);
                visited[i] = false;
            }
        }
    }
}

 

정말 간단하게 끝난다 ㄷㄷ

 

<핵심>

1. 가능한 경로가 2개 이상 나오는 경우에 알파벳 오름차순으로 정렬하기 쉽게 하기 위해 이동 경로를 String 타입으로 저장한다.

2. 티켓은 빠짐없이 모두 사용해야 하므로 visited[] 배열과 cnt 변수를 사용해서 티켓 사용 유무를 체크한다.

3. dfs 탐색 이후 다른 경로로도 빠질 수 있어야 하기 때문에 dfs 호출 이후 visited를 다시 false로 빼줘야 한다

 

 

나중에 다시 풀어볼것!!

 

 

+ 그리고 이건 첫 통과 코드를 약간 개선한 버전

- 경로 우선순위 비교를 쉽게 하기 위해 경로를 String으로 받을 수 있도록 개선. 기존 arr 배열은 그대로 사용하고 마지막에 StringBuilder를 사용해서 문자열을 합치는 방식으로 고쳤다.

- airportToIdx 맵이랑 idxToAirport 맵을 하나로 합치고 싶은데 마땅한 생각이 나지 않아서 그냥 뒀다..

- dfs를 쓴다고 꼭 그래프를 만들어야 하는 것이 아님을 알자!!

import java.util.*;

class Solution {

    private static class Edge {
        public int to; // 목적지
        public int weight; // 가중치

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    Map<String, Integer> airportToIdxMap = new HashMap<>();
    Map<Integer, String> idxToAirportMap = new HashMap<>();
    List<List<Edge>> adjList = new LinkedList<>();
    List<String> pathList = new ArrayList<>();
    int[] arr;

    public String[] solution(String[][] tickets) {

        airportToIdxMap.put("ICN", 0);
        idxToAirportMap.put(0, "ICN");
        adjList.add(new LinkedList<>());

        int idx = 1;
        for (String[] ticket : tickets) {
            // 고유 공항 추가
            if (!airportToIdxMap.containsKey(ticket[0])) {
                airportToIdxMap.put(ticket[0], idx);
                idxToAirportMap.put(idx++, ticket[0]);
                adjList.add(new LinkedList<>());
            }
            if (!airportToIdxMap.containsKey(ticket[1])) {
                airportToIdxMap.put(ticket[1], idx);
                idxToAirportMap.put(idx++, ticket[1]);
                adjList.add(new LinkedList<>());
            }

            // 연결 리스트 추가
            List<Edge> dept = adjList.get(airportToIdxMap.get(ticket[0]));
            boolean hasEdge = false;
            for (Edge edge : dept) {
                if (edge.to == airportToIdxMap.get(ticket[1])) {
                    edge.weight++;
                    break;
                }
            }
            if (!hasEdge) {
                dept.add(new Edge(airportToIdxMap.get(ticket[1]), 1));
            }
        }
        
        arr = new int[tickets.length + 1];
        arr[0] = 0;
        dfs(1, 0); // 0번(ICN) 출발 고정

        Collections.sort(pathList);
        return pathList.get(0).split(",");
    }

    public void dfs(int depth, int v) {
        // 모든 티켓을 다 사용했으면
        if (depth == arr.length) {
            StringBuilder sb = new StringBuilder();
            for (int val : arr) {
                sb.append(idxToAirportMap.get(val));
                sb.append(",");
            }
            System.out.println(sb.toString());
            pathList.add(sb.toString());
            return;
        }

        List<Edge> edges = adjList.get(v);
        for (Edge edge : edges) {
            if (edge.weight > 0) {
                edge.weight -= 1;
                arr[depth] = edge.to;
                dfs(depth + 1, edge.to);
                edge.weight += 1;
            }
        }
    }
}