꿀잠

https://leetcode.com/problems/word-ladder/description/

시작 단어부터 끝 단어까지 한 글자씩 변경할 때 몇 회에 변경 가능한지 묻는 문제이다. 이 때 변경 가능한 문자열은 리스트로 주어진다.

문제를 해결하기 위해서 BFS를 사용하여 해결하였다. 최소 거리를 묻는 문제이기 때문에 가까운 거리 부터 체크하는 BFS가 적절하고, 그래프의 형태는 각 글자를 각 알파벳으로 변경했을 때 주어진 리스트에 있는지로 확인해서 순차적으로 확인할 수 있다. 이 때 방문 체크는 문자열로 해야 하기 때문에 Set을 이용해 주었다.

import java.util.*;  
  
class Solution {  
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {  
        Queue<Object[]> que = new ArrayDeque<>();  
        Set<String> isExist = new HashSet<>();  
  
        que.add(new Object[]{beginWord, 1});  
        wordList.forEach(word -> isExist.add(word));  
  
        int answer = 0;  
        while(!que.isEmpty()){  
            Object[] info = que.poll();  
            String str = (String)info[0];  
            int cnt = (int)info[1];  
  
            if(cnt > wordList.size() + 1){  
                return answer;  
            }  
  
            if(str.equals(endWord)){  
                answer = cnt;  
                break;  
            }  
  
            char[] charArr = str.toCharArray();  
            for(int i = 0; i < charArr.length; i++){  
                char save = charArr[i];  
                for(int j = 0; j < 26; j++){  
                    charArr[i] = (char)(j + 'a');  
                    String next = new String(charArr);  
                    if(isExist.contains(next) && (charArr[i] != save)){  
                        que.add(new Object[]{next, cnt + 1});  
                        isExist.remove(next);  
                    }  
                }  
                charArr[i] = save;  
            }  
        }  
  
        return answer;  
    }  
}

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});  
                    }  
                }  
            }  
        }  
    }  
}

특정 강의를 듣기 위해서 다른 강의를 들어야 하는 정보가 주어질 때 정상적으로 강의를 들을 수 있는 지에 대한 문제이다. 강의의 관계가 순환 참조 되는 경우 불가능하다고 판단해야 한다.

처음에는 dfs 백트래킹 방식으로 해결하려 하였으나 시간 초과가 되었다. 알고리즘을 바꿔야 하나 고민도 했지만 같은 관계를 여러 번 반복해서 검사를 수행하는 경우가 생긴다는 문제를 알게 되었다. 동일 경로에 대해 어떻게 처리할까 고민하던 중 일반적인 visited를 boolean으로 사용하는 방식 대신 int를 이용하여 미방문,방문,경로완료의 형태로 세가지 상태로 visited 배열을 관리하여 해결해 보았다. 결과적으로 시간 초과의 문제를 해결하고 통과할 수 있었다.

import java.util.*;  
  
public class Solution {  
  
    static int VISITED = 1;  
    static int COMPLETE = 2;  
  
    public boolean canFinish(int numCourses, int[][] prerequisites) {  
        List<Integer>[] preCourse = new ArrayList[numCourses];  
        for(int i = 0; i < numCourses; i++){  
            preCourse[i] = new ArrayList<Integer>();  
        }  
  
        for(int[] info : prerequisites){  
            int course = info[0];  
            int need = info[1];  
  
            preCourse[course].add(need);  
        }  
  
        int[] visited = new int[numCourses];  
        for(int i = 0; i < numCourses; i++){  
            if(preCourse[i].isEmpty()) continue;  
            if(!isPossible(i, preCourse, visited)){  
                return false;  
            }  
        }  
  
        return true;  
    }  
  
    private boolean isPossible(int course, List<Integer>[] preCourse, int[] visited){  
  
        if(visited[course] == COMPLETE){  
            return true;  
        }  
  
        if(visited[course] == VISITED){  
            return false;  
        }  
  
        visited[course] = VISITED;  
  
        for(int pre: preCourse[course]){  
            if(!isPossible(pre, preCourse, visited)){  
                return false;  
            };  
        }  
  
        visited[course] = COMPLETE;  
        return true;  
    }  
  
}

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/pacific-atlantic-water-flow/description/

주어진 좌표가 두 가지 해역으로 둘러 쌓여있고, 높이 값일 때 높은 곳에서 낮은 곳으로 홍수로 인해 물이 흐른다. 이 때 양쪽 해역으로 물이 다 흐르는 좌표를 찾는 문제이다.

물이 흐를 수 있다는 것은 각 해변 좌표 쪽까지 도달할 수 있다는 것이다. 그렇기 때문에 역으로 해변 쪽 좌표에서 높아 지는 좌표들을 체크한다면 정답 좌표들을 찾아 나갈 수 있다. 이 때 해역이 두 가지 이므로 visited 배열을 두 가지 사용한 이후 두 visited 모두를 확인하여 정답 목록을 체크할 수 있다. bfs방식으로 그래프를 탐색했으면 완성 코드는 아래와 같다.

import java.util.*;  
  
public class Solution {  
    public List<List<Integer>> pacificAtlantic(int[][] heights) {  
        int m = heights.length;  
        int n = heights[0].length;  
        boolean[][] pacific = new boolean[m][n];  
        boolean[][] atlantic = new boolean[m][n];  
        List<List<Integer>> answer = new ArrayList<>();  
        for(int i = 0; i < m; i++){  
            for(int j = 0; j < n; j++){  
                // pacific,북쪽  
                if(i == 0){  
                    bfs(i, j, heights, pacific);  
                // pacific,서쪽  
                }else if(j == 0){  
                    bfs(i, j, heights, pacific);  
                }  
  
                // atlantic,동쪽  
                if(i == m - 1){  
                    bfs(i, j, heights, atlantic);  
                // atlantic,남쪽  
                }else if(j == n - 1){  
                    bfs(i, j, heights, atlantic);  
                }  
            }  
        }  
  
        for(int i = 0; i < m; i++){  
            for(int j = 0; j <n; j++){  
                if(pacific[i][j] && atlantic[i][j]) answer.add(List.of(i, j));  
            }  
        }  
  
        return answer;  
    }  
  
    private void bfs(int r, int c, int[][] heights, boolean[][] visited){  
        int[] dr = {-1,0,1,0};  
        int[] dc = {0,-1,0,1};  
  
        Queue<int[]> que = new ArrayDeque<>();  
        que.add(new int[]{r, c});  
  
        while(!que.isEmpty()){  
            int[] now = que.poll();  
            int row = now[0];  
            int col = now[1];  
            if(visited[row][col]){  
                continue;  
            }  
  
            visited[row][col] = true;  
  
            for(int dir = 0; dir < 4; dir++){  
                int nextRow = row + dr[dir];  
                int nextCol = col + dc[dir];  
  
                if(nextRow >= 0 && nextRow < heights.length  
                        && nextCol >= 0 && nextCol < heights[0].length  
                        && !visited[nextRow][nextCol]  
                        && heights[nextRow][nextCol] >= heights[row][col]){  
                    que.add(new int[]{nextRow, nextCol});  
                }  
            }  
  
        }  
    }  
  
}

https://leetcode.com/problems/number-of-islands/description/

주어진 그리드에서 땅으로 연결된 섬이 몇 개인지 체크하는 문제이다.
bfs를 이용하여 땅인 부분 확인하고 섬의 개수를 확인하였으며, 이때 땅을 확인할 때 bfs를 이용하여 연결된 모든 땅을 CHECK_LAND로 변경하여 연결된 땅을 샐 수 있도록 하였다.

import java.util.*;  
  
public class Solution {  
  
    private static final char LAND = '1';  
    private static final char WATER = '0';  
    private static final char CHECK_LAND = '3';  
  
    public int numIslands(char[][] grid) {  
        int cnt = 0;  
  
        for (int i = 0; i < grid.length; i++) {  
            for (int j = 0; j < grid[0].length; j++) {  
                if (bfs(i, j, grid)) {  
                    cnt++;  
                }  
                ;  
            }  
        }  
  
        return cnt;  
    }  
  
    private boolean bfs(int row, int col, char[][] grid) {  
        // 현재 좌표가 땅인지 확인  
        if (grid[row][col] != LAND) {  
            return false;  
        }  
  
        // 땅일 경우 최종적으로 true return, return 이전에 연결된 땅을  
        // bfs로 CHECK_LAND로 바꾸어 둔다. 연결된 땅은 땅으로 확인되지 않으므로  
        // 연결된 땅 전체를 하나로 확인 가능하다.  
        grid[row][col] = CHECK_LAND;  
  
        // 아래, 좌, 위, 우 각 방향 별로 확인하기 위한 방향 배열  
        int[] dr = {-1, 0, 1, 0};  
        int[] dc = {0, -1, 0, 1};  
  
        // que 에 넣기 위해 Pos class를 만들어서 이용, int[] 을 사용해도 무방하다.  
        Queue<Pos> que = new ArrayDeque<>();  
        que.add(new Pos(row, col));  
  
        while (!que.isEmpty()) {  
            Pos cur = que.poll();  
            for (int i = 0; i < 4; i++) {  
                int nextr = cur.r + dr[i];  
                int nextc = cur.c + dc[i];  
  
                // 그리드 범위조건, 땅인 부분의 경우 CHECK로 변환  
                if (nextr >= 0  
                        && nextr < grid.length  
                        && nextc >= 0  
                        && nextc < grid[0].length  
                        && grid[nextr][nextc] == LAND  
                ) {  
                    grid[nextr][nextc] = CHECK_LAND;  
                    que.add(new Pos(nextr, nextc));  
                }  
            }  
        }  
  
        return true;  
    }  
  
    private class Pos {  
        int r;  
        int c;  
  
        Pos(int r, int c) {  
            this.r = r;  
            this.c = c;  
        }  
    }  
}

연결된 땅을 하나씩 샐 수 있도록 bfs 를 이용하여 푼 문제였다, 각 방향으로 bfs 그래프를 탐색하며, 그리드의 범위, 땅인지 아닌지를 체크할 때 조건을 잘 확인해야한다.