<commit_before>---
layout: post
title: coding Interview Prep - DFS && BFS
modified: 2019-09-03
tags: [codingIntervewPrep]
---

# DFS

DFS는 간단힌 recursion과 stack을 이용한 iteration으로 구현할 수 있다. 
 
## Recursion Flow

```java
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

```java
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

```java
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<Integer> stack = new Stack<Integer>(); 
- 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<Integer> 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

```java
Math.min(), Min.max()  
```

## Max and Min value

```java
Interger.Min_Value, Interger.Max_Value
```

## 간단히 x, y 좌표를 Stack에 넣고 빼기

```java
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에 넣고 빼기

```java
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
int[] s = queue.poll();
int y = s[0];
int x = s[1];
```

## 간단히 4방향 순회하기 

```java
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으로 한것을 각각 구현하였다.

```java
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];<commit_msg>fix: wrong tag<commit_after>---
layout: post
title: coding Interview Prep - DFS && BFS
modified: 2019-09-03
tags: [codingIntervewPrep]
---

# DFS

DFS는 간단힌 recursion과 stack을 이용한 iteration으로 구현할 수 있다. 
 
## Recursion Flow

```java
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

```java
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

```java
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<Integer> stack = new Stack<Integer>(); 
- 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<Integer> 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

```java
Math.min(), Min.max()  
```

## Max and Min value

```java
Interger.Min_Value, Interger.Max_Value
```

## 간단히 x, y 좌표를 Stack에 넣고 빼기

```java
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에 넣고 빼기

```java
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
int[] s = queue.poll();
int y = s[0];
int x = s[1];
```

## 간단히 4방향 순회하기

```java
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으로 한것을 각각 구현하였다.

```java
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];
{'fraction_non_alphanumeric': 0.13248421510994993, 'fraction_numerical': 0.010450685826257348, 'mean_word_length': 2.1766943291839556, 'pattern_counts': {'":': 0, '<': 39, '<?xml version=': 0, '>': 27, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '520968', 'n_tokens_mistral': 4215, 'n_tokens_neox': 4657, 'n_words': 1293}