꿀잠

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

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/clone-graph/description/

주어진 그래프 노드를 깊은 복사 하는 함수를 만드는 문제이다.
깊은 복사를 해야 하므로 주어진 클래스와 연결된 노드는 모두 새로 생성되고 값을 복사해야한다.
주어진 조건으로 1 ~ 100 까지이고, 각 노드는 유니크 하다는 조건을 이용해 copy 배열과 bfs를 만들어서 이용해주었다.

package ygs.leetcode.main.problem.graphs.cloneGraph;  
  
/*  
// Definition for a Node.  
class Node {  
    public int val;    
    public List<Node> neighbors;    
    public Node() {        
	    val = 0;        
	    neighbors = new ArrayList<Node>();    
	}    
	
	public Node(int _val){
	        val = _val;
	        neighbors = new ArrayList<Node>();    
	}    
	
	public Node(int _val, ArrayList<Node> _neighbors) {        
		val = _val;        
		neighbors = _neighbors;    
	}}  
*/  
  
import java.util.*;  
  
public class Solution {  
    public Node cloneGraph(Node node) {  
        if(node == null) return null;  
  
        Node[] copys = new Node[101];  
        List[] copyLists = new ArrayList[101];  
        boolean[] visited = new boolean[101];  
  
        Queue<Node> que = new ArrayDeque<>();  
        que.add(node);  
  
        while(!que.isEmpty()){  
            Node origin = que.poll();  
            List<Node> orgNeighbors = origin.neighbors;  
  
            if(visited[origin.val]) continue;  
            visited[origin.val] = true;  
  
            Node copy = getOrCreate(copys, origin.val);  
            copyLists[origin.val] = copy.neighbors;  
            List<Node> copyList = copyLists[origin.val];  
  
            copys[origin.val].neighbors = copyLists[origin.val];  
  
            for(Node originNeighbor: orgNeighbors){  
                int neighborVal = originNeighbor.val;  
                copyList.add(getOrCreate(copys, neighborVal));  
  
                if(!visited[originNeighbor.val]){  
                    que.add(originNeighbor);  
                }  
            }  
        }  
  
        return copys[node.val];  
    }  
  
    private Node getOrCreate(Node[] copys, int val){  
        if(copys[val] == null){  
            copys[val] = new Node(val);  
        }  
  
        return copys[val];  
    }  
}