꿀잠

https://leetcode.com/problems/reconstruct-itinerary/description/

주어진 티켓을 모두 사용해서 여행 계획을 짜는 문제이다. 이 때 완성된 여행 일정의 문자의 사전 순서가 빠른 순서인 것이 최종 정답이다.

문자의 속도가 중요하여 PriorityQueue를 이용해서 BFS를 처음에 시도했다. 하지만 시간 초과에 걸려 다른 방법들을 시도하다가 결국 정답 정보를 찾아보게 되었다. 사전 순서를 지키기 위해 PriorityQueue를 이용하고 DFS를 하는 방식이었다. 이 때 각 티켓, 사전 순으로 순환 하고 순환이 완료 된 이후에는 정답 리스트에 문자열을 추가한다.

PriorityQueue 에서 poll 하면서 순환하기 때문에 DFS 메서드에 최종 진입한 역은 다음 그래프가 없기 때문에 정답에 바로 추가 된다. 이처럼 메서드가 재귀적으로 역순 순환될 때 완료한 순서대로 정답이 추가된다. 이 때 역순으로 되기 때문에 addFirst 함수를 이용해서 역으로 정답에 담아 리턴 했다. 아래는 최종 통과 코드이다.

import java.util.*;  
  
public class Solution {  
  
    List<String> answer;  
  
    public List<String> findItinerary(List<List<String>> tickets) {  
  
        Map<String, PriorityQueue<String>> graphs = new HashMap<>();  
        answer = new ArrayList<>();  
  
        int ticketCnt = 0;  
        for(List<String> ticket: tickets){  
            String from = ticket.get(0);  
            String to = ticket.get(1);  
            if(!graphs.containsKey(from)){  
                graphs.put(from, new PriorityQueue<>());  
            }  
  
            graphs.get(from).add(to);  
        }  
  
        dfs("JFK", graphs);  
  
        return answer;  
    }  
  
    private void dfs(String airport, Map<String, PriorityQueue<String>> graphs){  
        PriorityQueue<String> graph = graphs.get(airport);  
        while(graph != null && !graph.isEmpty()){  
            dfs(graph.poll(), graphs);  
        }  
  
        answer.addFirst(airport);  
    }  
}

https://leetcode.com/problems/swim-in-rising-water/

각 좌표에 물이 차올라 있어 최소 통과 가능 시간이 정해져 있을 때 최종 좌표까지 도달할 수 있는 최소 시간을 구하는 문제이다. bfs 그래프 문제로 순환하며 풀었으며, 제한 사항을 관리하기 위하여 최소방문 시간 그리드를 이용하였다.

특정 좌표 (r,c) 에 대하여 최소 통과 가능 시간은 해당 그리드의 값이고, 실제로 통과한 시간은 다른 그리드를 거쳐 도착했을 때의 최소 시간이다. 다른 그리드를 거쳐 도착했을 때의 시간이 해당 그리드의 최소 시간 이전일 경우 해당 그리드에서 해당 시간까지 대기해야 하기 때문에 Math.max를 이용하여 시간을 체크 해주었다. 또한 다른 경로로 도착했을 때 그보다 빠르게 도착하는 방법이 있을 경우 해당 순환은 불필요하기에 크기 비교를 통하여 경로 필터를 해주었다. 아래는 최종 통과코드이다.

import java.util.*;  
  
public class Solution {  
  
    public int swimInWater(int[][] grid) {  
  
        int m = grid.length;  
        int n = grid[0].length;  
        int[][] minTimes = new int[m][n];  
        for(int i = 0; i < m; i++){  
            Arrays.fill(minTimes[i], Integer.MAX_VALUE);  
        }  
        minTimes[0][0] = grid[0][0];  
        bfs(grid, minTimes);  
  
        return minTimes[m - 1][n - 1];  
    }  
  
    private void bfs(int[][] grid, int[][] minTimes){  
  
        int[] dr = {-1,0,1,0};  
        int[] dc = {0,-1,0,1};  
  
        Queue<int[]> q = new ArrayDeque<>();  
        q.add(new int[]{0,0});  
  
        while(!q.isEmpty()){  
            int[] now = q.poll();  
            int r = now[0];  
            int c = now[1];  
  
            for(int i = 0; i < 4; i++){  
                int nextRow = r + dr[i];  
                int nextCol = c + dc[i];  
                int time = minTimes[r][c];  
  
                if(nextRow >= 0 && nextRow < grid.length  
                        && nextCol >= 0 && nextCol < grid[0].length  
                ){  
                    int nextTime = Math.max(time, grid[nextRow][nextCol]);  
                    if(minTimes[nextRow][nextCol] > nextTime){  
                        minTimes[nextRow][nextCol] = nextTime;  
                        q.add(new int[]{nextRow, nextCol});  
                    }  
                }  
            }  
        }  
    }  
}

https://leetcode.com/problems/cheapest-flights-within-k-stops/

정해진 경유지 수 이내에서 목적지까지 가장 적은 비용으로 도달하는 방법을 찾는 문제이다.
목적지까지 최단 비용 문제의 경우 다익스트라 알고리즘을 이용해줄 수 있다.

해당 문제 또한 다익스트라 알고리즘으로 해결할 수 있으며, 특이점으로는 경유지 숫자에 제한이 있다는 점이다. 따라서 PriorityQueue를 이용하여 경로를 설정할 때 경유지 개수를 포함 시켜 문제를 해결하였다.

public class Solution {  
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {  
        List<Route>[] prices = new ArrayList[n];  
        for(int i = 0; i < n; i++){  
            prices[i] = new ArrayList<>();  
        }  
  
        PriorityQueue<Route> pq = new PriorityQueue<>((a, b) -> {  
            if(a.stop == b.stop){  
                return a.price - b.price;  
            }  
            return a.stop - b.stop;  
        });  
  
        for(int[] flight: flights){  
            int from = flight[0];  
            int to = flight[1];  
            int price = flight[2];  
  
            prices[from].add(new Route(to, price, 0));  
        }  
  
        for(Route route: prices[src]){  
            pq.add(route);  
        }  
  
        int[] minValue = new int[n];  
        Arrays.fill(minValue, Integer.MAX_VALUE);  
        while(!pq.isEmpty()){  
            Route now = pq.poll();  
            int to = now.to;  
            int price = now.price;  
            int stop = now.stop;  
            if(k < stop){  
                continue;  
            }  
  
            if(minValue[to] < price){  
                continue;  
            }  
  
            minValue[to] = price;  
  
            for(Route next: prices[to]){  
                int nextTo = next.to;  
                int nextPrice = price + next.price;  
                int nextStop = stop + 1;  
                if(minValue[nextTo] > nextPrice){  
                    pq.add(new Route(nextTo, nextPrice, nextStop));  
                }  
            }  
        }  
  
        return minValue[dst] == Integer.MAX_VALUE ? -1 : minValue[dst];  
    }  
  
    private class Route{  
        int to;  
        int price;  
        int stop;  
  
        Route(int to, int price, int stop){  
            this.to = to;  
            this.price = price;  
            this.stop = stop;  
        }  
    }  
}

https://leetcode.com/problems/min-cost-to-connect-all-points/description/

좌표의 거리가 가장 가까운 거리에 있는 좌표끼리 이어주는 문제이다. 최소신장트리 알고리즘이 필요한 문제이다. 좌표간의 거리는 일반적인 거리가 아닌 manhattan distance를 이용해야 하며 문제에서 수식이 주어진다.

최소 신장 알고리즘에는 프림 알고리즘과 크루스칼 알고리즘이 대표적이다. 그 중 프림 알고리즘을 이용하여 풀어주었다.

프림 알고리즘은 임의의 한 지점부터 가장 가까운 거리에 있는 지점을 이어주면서 순차적으로 방문한 지점들을 visited로 체크해주는 방식이다. 순차적으로 가까운 거리를 이어주기 위해서 PriorityQueue를 사용해 주었고 주어진 수식을 이용하기 위해 Comparable을 구현한 클래스를 만들어주었다.

import java.util.*;  
  
public class Solution {  
    public int minCostConnectPoints(int[][] points) {  
  
        int answer = 0;  
        boolean[] visited = new boolean[points.length];  
        PriorityQueue<Edge> pq = new PriorityQueue<>();  
        pq.add(new Edge(0, 0, points));  
  
        while(!pq.isEmpty()){  
            Edge edge = pq.poll();  
            int cur = edge.to;  
            if(visited[cur]) continue;  
            visited[cur] = true;  
            answer += edge.dist;  
  
            for(int next = 0; next < points.length; next++){  
                if(next == cur) continue;  
                if(!visited[next]){  
                    pq.add(new Edge(cur, next, points));  
                }  
            }  
        }  
  
        return answer;  
    }  
  
    private static class Edge implements Comparable<Edge>{  
        int from;  
        int to;  
        int dist;  
  
        Edge(int from, int to, int[][] points){  
            this.from = from;  
            this.to = to;  
            this.dist = manDist(points[from], points[to]);  
        }  
  
        private int manDist(int[] from, int[] to){  
            int xCalc = Math.abs(from[0] - to[0]);  
            int yCalc = Math.abs(from[1] - to[1]);  
            return xCalc + yCalc;  
        }  
  
        @Override  
        public int compareTo(Edge o){  
            return this.dist - o.dist;  
        }  
  
    }  
  
}

https://leetcode.com/problems/network-delay-time/description/

주어진 노드로 부터 최단 경로를 묻는 다익스트라 알고리즘을 사용하는 문제였다.
예전에 공부했었는데 잘 기억이 나지 않아 복습하며 풀었다. 처음에 오래된 기억으로 더듬 거리며 풀다보니 시간 초과가 나왔다. 복습하며 잘못된 부분들을 해결 하며 풀었다.

다익스트라는 주어진 시작점으로 부터 최단 경로를 기준으로 경로를 이어 나가는 그리디 + DP 형식의 그래프 문제이다. 최단경로를 이어나가기 위해 PriorityQueue 사용했으며, 각 경로의 최소 길이를 배열에 저장하여 DP 배열로 활용하였다.

import java.util.*;  
  
public class Solution {  
    public int networkDelayTime(int[][] times, int n, int k) {  
  
        // node 정보를 담을 List 초기화  
        List<Node>[] nodes = new List[n + 1];  
        for(int i = 0; i < nodes.length; i++){  
            nodes[i] = new ArrayList<>();  
        }  
  
        for(int[] time: times){  
            int from = time[0];  
            int to = time[1];  
            int travel = time[2];  
            // node 정보 List에 담기  
            nodes[from].add(new Node(to, travel));  
        }  
  
        // 다익스트라 알고리즘을 사용하기 위한 pq        
        // 최단경로를 저장하기 위한 travels        
        PriorityQueue<Node> pq = new PriorityQueue<>();  
        int[] travels = new int[n + 1];  
  
        // 최단경로 무한대로 초기화  
        for(int i = 1; i < travels.length; i++){  
            travels[i] = Integer.MAX_VALUE;  
        }  
  
        // 시작지점 처리  
        travels[k] = 0;  
        pq.add(new Node(k, 0));  
  
        while(!pq.isEmpty()){  
            Node cur = pq.poll();  
  
            // 현재 지점까지 최단 경로인지 확인, visited 체크 역할  
            if (cur.travel > travels[cur.node]){  
                continue;  
            }  
  
            // 다음 경로 확인  
            for (Node next : nodes[cur.node]) {  
                int newTravel = cur.travel + next.travel;  
                // 다음 경로중 최단경로인 경우 pq 경로 추가  
                if (newTravel < travels[next.node]) {  
                    travels[next.node] = newTravel;  
                    pq.add(new Node(next.node, newTravel));  
                }  
            }  
        }  
  
        int answer = 0;  
        for(int i = 1; i < travels.length; i++){  
            // 가장 오래 걸린 경우 Network Delay를 마친 시간  
            answer = Math.max(travels[i], answer);  
        }  
  
        // 도달하지 못한경우 초기 거리값을 가지고 있으므로 -1, 아니면 answerreturn answer == Integer.MAX_VALUE ? -1 : answer;  
    }  
  
    private static class Node implements Comparable<Node>{  
        int node;  
        int travel;  
  
        Node(int node, int travel){  
            this.node = node;  
            this.travel = travel;  
        }  
  
        @Override  
        public int compareTo(Node o){  
            return Integer.compare(this.travel, o.travel);  
        }  
    }  
}