Keep learning and keep sharing

DFS
DFS는 간단힌 recursion과 stack을 이용한 iteration으로 구현할 수 있다.
Recursion Flow
function(g, s) //g는 graph, s는 시작 vertex
	visited를 false(미방문상태)로 초기화 
	시작점 s를 방문한 것으로 표시 //visited에서 s를 true로 설정
	process(g, visited, s)
process(g, visited, s) //g는 graph, s는 시작 vertex
  skip 조건 확인 // outOfBound, 이미 방문 했는지, 기타 skip 조건에 해당하는지
	종료 조건 확인 
	인접 vertex loop
		v <- next v
		visited[v] = true
		process(g, visited, v)
		visited[v] = false // 이것은 모든 경우의 수를 테스트 하는 경우 사용
Iteration Flow
function(g, s) //g는 graph, s는 시작 vertex
  stack 초기화 
  visited[]를 false(미방문상태)로 초기화
  시작점 s를 방문한 것으로 표시 //visited[]에서 s를 true로 설정
  stack에 s를 삽입//push
  while(stack이 비어있지 않으면)
     v <- stack에서 pop
     for(u <- v와 인접한 vertex들)  
        if(skip 조건 확인) {   // outOfBound, 이미 방문 했는지, 기타 skip 조건에 해당하는지
          continue;
        }
        종료 조건 확인
        방문으로 표시 //visited[]에서 u를 true로 설정
        u를 stack에 push
BFS
BFS는 queue를 이용해 구현할 수 있다.
Iteration Flow
function(g, s) //g는 graph, s는 시작 vertex
  queue 초기화 
  visited[]를 false(미방문상태)로 초기화
  시작점 s를 방문한 것으로 표시 //visited[]에서 s를 true로 설정
  stack에 s를 삽입//offer
  while(queue가 비어있지 않으면)
		size <- q.size() 
    while size-- > 0 // 현재 queue에 있는 아이템에 대해서 모두 (한 레벨씩)
	     v <- queue에서 poll
	     for(u <- v와 인접한 vertex들)  
	        if(skip 조건 확인) {   // outOfBound, 이미 방문 했는지, 기타 skip 조건에 해당하는지
	          continue;
	        }
	        종료 조건 확인
	        방문으로 표시 //visited[]에서 u를 true로 설정
	        u를 queue에 offer
Java
Stack
초기화: Stack stack = new Stack();
Object push(Object element)
Object peek() : Returns the element on the top of the stack, but does not remove it.
Object pop() : Removes and returns the top element of the stack. An ‘EmptyStackException’ exception is thrown if we call pop() when the invoking stack is empty.
boolean isEmpty() : It returns true if nothing is on the top of the stack. Else, returns false.
Queue
초기화: Queue q = new LinkedList<>();
offer(): This method is used to add elements at the tail of queue. = add()
peek(): This method is used to view the head of queue without removing it. It returns Null if the queue is empty.
poll(): This method removes and returns the head of the queue. It throws NoSuchElementException when the queue is empty. = remove()
boolean isEmpty() : It returns true if nothing is on the top of the stack. Else, returns false.
Min and Max
Math.min(), Min.max()  
Max and Min value
Interger.Min_Value, Interger.Max_Value
간단히 x, y 좌표를 Stack에 넣고 빼기
Stack<int[]> stack = new Stack<>();
stack.push(new int[]{i, j});
int[] s = stack.pop();
int y = s[0];
int x = s[1];
간단히 x, y 좌표를 Queue에 넣고 빼기
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
int[] s = queue.poll();
int y = s[0];
int x = s[1];
간단히 4방향 순회하기
int[][] dirs = new int[][]{ {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
for (int[] dir : dirs) {
	int nextY = dir[0];
	int nextX = dir[1];
}
예제 문제
https://leetcode.com/problems/shortest-bridge/
두개의 island를 잊는 가장 짧은 다리를 구하는 것이다. 1이 육지이고 0이 바다이다. 
1을 찾은 후 그것의 DFS를 그려서 모두 visited로 마크하고 queue에 집어 넣는다. 이제 queue에서 하나씩 빼내어 주변을 탐색한다.
만약 visited가 아니면 하나씩 돌면서 queue에 다시 넣고, 방문한 것으로 처리한다. 이것은 한 레벨씩 증가하면서 탐색을 하고 
만약 값이 1인데 visited가 아닌 것을 만나면 이때의 step의 숫자를 출력한다.
아래는 BFS와 DFS를 사용한 것인데, DFS를 recursion으로 한것과 iteration으로 한것을 각각 구현하였다.
class Solution {
    public int shortestBridge(int[][] A) {
        int m = A.length, n = A[0].length;
        boolean[][] visited = new boolean[m][n];
        int[][] dirs = new int[][]{ {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        Queue<int[]> q = new LinkedList<>();
        boolean found = false;
        // 1. dfs to find an island, mark it in `visited`
        for (int i = 0; i < m; i++) {
            if (found) {
                break;
            }
            for (int j = 0; j < n; j++) {
                if (A[i][j] == 1) {
                    dfs(A, visited, q, i, j, dirs);
                    found = true;
                    break;
                }
            }
        }
        // 2. bfs to expand this island
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                int[] cur = q.poll();
                for (int[] dir : dirs) {
                    int i = cur[0] + dir[0];
                    int j = cur[1] + dir[1];
                    if (i >= 0 && j >= 0 && i < m && j < n && !visited[i][j]) {
                        if (A[i][j] == 1) {
                            return step;
                        }
                        q.offer(new int[]{i, j});
                        visited[i][j] = true;
                    }
                }
            }
            step++;
        }
        return -1;
    }
    // DFS by recursion
  private void dfs(int[][] A, boolean[][] visited, Queue<int[]> q, int i, int j, int[][] dirs) {
        Stack<int[]> stack = new Stack<>();
        visited[i][j] = true;
        q.offer(new int[]{i, j}); //Insert all the 1s of island to the queue 
        stack.push(new int[]{i, j});
        while (!stack.isEmpty()) {
            int[] s = stack.pop();
            int y = s[0];
            int x = s[1];
            for (int[] dir : dirs) {
                int nextY = y + dir[0];
                int nextX = x + dir[1];
                if (nextY < 0 || nextX < 0 || nextY >= A.length || nextX >= A[0].length || visited[nextY][nextX] || A[nextY][nextX] == 0) {
                    continue;
                }
                visited[nextY][nextX] = true;
                q.offer(new int[]{nextY, nextX}); //Insert all the 1s of island to the queue 
                stack.push(new int[]{nextY, nextX});
            }
        }
    }
	// DFS by recursion
	private void dfs(int[][] A, boolean[][] visited, Queue<int[]> q, int i, int j, int[][] dirs) {
        if (i < 0 || j < 0 || i >= A.length || j >= A[0].length || visited[i][j] || A[i][j] == 0) {
            return;
        }
        visited[i][j] = true;
        q.offer(new int[]{i, j}); //Insert all the 1s of island to the queue 
        for (int[] dir : dirs) {
            dfs(A, visited, q, i + dir[0], j + dir[1], dirs);
        }
    }
}
기타 Leetcode 문제들
leetcode에 있는 DFS관련한 문제를 풀어보자. 모두 hard difficulty의 문제들이다.
Unique Paths III: https://leetcode.com/problems/unique-paths-iii/
https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/
https://leetcode.com/problems/making-a-large-island/
https://leetcode.com/problems/contain-virus/
https://leetcode.com/problems/minimize-malware-spread/
https://leetcode.com/problems/sum-of-distances-in-tree/
https://leetcode.com/problems/remove-boxes/
https://leetcode.com/problems/binary-tree-cameras/
https://leetcode.com/problems/similar-string-groups/

coding Interview Prep - DFS && BFS

댓글