DFS & BFS

• 탐색(search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 대표적 그래프 탐색 알고리즘 DFS & BFS

스택 자료구조

• 먼저 들어온 데이터가 나중에 나가는 형식의 자료구조(선입후출)
• 입구와 출구가 동일한 형태로 스택을 시각화할 수 있음
• 삽입과 삭제 둘로 이루어짐

큐 자료구조

• 먼저 들어 온 데이터가 먼저 나가는 형식의 자료구조(선입선출)
• 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화

재귀 함수

• 자기 자신을 다시 호출하는 함수
• 단순한 형태의 재귀함수 예제
  - 재귀 함수를 호출합니다. 라는 문자를 무한히 출력
  • 어느정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력
• 재귀 함수를 문제 풀이에서 사용할 때는 재귀함수 종료 조건 반드시 명시

<팩토리얼 구현 예제>

• 반복적으로 구현한 n!

function factorial(n) {
	result = 1
  	for (i = 0; i <= n; i++) {
    	result *= i
    }
 return result
}

• 재귀적으로 구현한 n!

function factorial_recursive(n) {
	if (n <= 1) {
    	return 1
    }
 return n * factoriacl_recursive(n -1)
}

<최대공약수 (유클리드 호제법) 예제>

• 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘으로 유클리드 호제법
• 유클리드 호제법
  - 두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 합시다.
  • 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같음
• 유클리드 호제법의 아이디어를 그대로 재귀함수로 작성할 수 있음

function gcd(a, b) {
	if (a % b === 0) {
    	return b
    }
   return gcd(b, a % b)
}

-컴퓨터 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택프레임에 쌓임
-그래서 스택을 사용할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많음

DFS(Deptch -First Search)

• 깊이를 우선으로 하여 탐색하는 알고리즘
• DFS는 스택 자료구조를 이용, 구체적인 동작은 다음과 같음
  1)탐색 시작 노드를 스택에 삽입하고 방문처리
  2)스택의 최상단 노드에 방문하지않는 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리함, 방문하지않는 인접노드가 없으면 스택에서 최상단 노드를 꺼냄
  3)더 이상 2번의 과정 수행할수 없을때까지 반복

let graph = [
	[],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]
let visited = [False] * 9 //각 노드를 아직 방문하지 않음

function dfs(graph, v, visited) {
	visited[v] = True
	for (let i = 0; i < graph[v].length; i++) {
    	if (visited[i] != False) {
        	dfs(graph, i, visted)
        }
    }
}

BFS(Breath - First Search)

• 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• BFS는 큐자료구조를 이용, 구체적인 동작은 다음과 같음
  1)탐색 시작 노드를 큐에 삽입하고 방문 처리를 함
  2)큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않는 노드를 모두 큐에 삽입하고 방문 처리함
  3)더 이상 2번의 과정을 수행할 수 없을 때까지 반복

let graph = [
	[],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

function bfs(graph, vertex, visited) {
  const queue = [vertex];
  visited[vertex] = true
	while (queue.length > 0) {
    	const current = queue.shift()
        for (let i = 0; i < graph[current].length; i++) {
        	if (!visited[graph[current][i]]) {
            	queue.push(graph[current][i]);
              visited[graph[current][i]) = true
            }
        }
    }
}

<문제> 음료수 얼려먹기

• N * M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시, 구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어있는 것으로 간주
  이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성

• DFS