꿀잠

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

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

처음에는 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/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];  
    }  
}

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 그래프를 탐색하며, 그리드의 범위, 땅인지 아닌지를 체크할 때 조건을 잘 확인해야한다.