[Algorithm] DFS, BFS

알고리즘 공부 계속 안했더니 바로 뇌가 초기화되어서 하나도 기억안난다...
근데 사실 당연함 원래 그렇게 잘하지도 못했음.. 늦었다고 생각될 때 일단 열심히하장. 

이건 아빠가 그리신 묘목

---

DFS (Depth-First Search)_깊이우선검색

1. 한 방향으로 모든 노드를 방문하다가
2. 더이상 다른 노드를 방문할 수 없는 노드에 이르렀을 때
3. 다시 가장 가까운 갈래길로 돌아가 방문하지 않은 노드 방향으로 탐색을 이어간다.
   1. 간선이나 변수 정보를 수시로 변경해야할 때 DFS를 활용한다.
   2. 한 노드를 시작으로 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색

이걸 구체적인 동작 과정을 정리하면…

1. 탐색 시작 노드 정보를 스택에 삽입하고 방문처리한다.
   1. 스택에 한번이라도 삽입된 노드를 다시 삽입하지 않도록 체크
   2. 탐색한 노드를 재방문하지 않도록 구분하는 것
2. 스택 내 최상단 노드의 방문하지 않은 인접 노드 정보를 스택에 삽입하고 방문처리 한다.
3. 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.

def dfs(graph, start, visted):
	if visited is None: 스택에 한번이라도 삽입된 노드를 다시 삽입하지 않도록 체크
		visited = set() 탐색한 노드를 재방문하지 않도록 구분하는 것
	visited.add(start) 탐색 시작 노드 정보를 스택에 삽입하고 방문처리한다 
	print(start) 노드 방문시 처리할 작업
	for next in graph[start]-visited: 스택 내 최상단 노드의 방문하지 않은 인접 노드정보를 스택에 삽입
		dfs(graph, next, visited) 그 경로에 대해 깊이탐색(자식노드로 이동)
	return visited

문제해결을 위해 dfs를 활용하는 알고리즘

1. 특정한 지점의 주변 상하좌우를 살펴본다.
2. 주변 지점 중에서 값이 ‘0’이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문
3. 방문한 지점에서 다시 상하좌우를 살펴보면서 방문을 진행하는 과정을 반복
   1. 연결된 모든 지점을 방문할 수 있다.
4. 모든 노드에 대하여 위 과정 반복

특정 노드와 연결된 모든 노드들을 방문할 수 있다. → 가능한 모든 경로를 찾을 수 있다.

언제 dfs를 쓸까?

1. 그래프 순회
2. 위상 정렬
   • [ ] 솔직히 이건 뭔지 잘 모르겠긴함 → 동빈나 이코테 8강 ㄱ
3. 그래프에서 사이클 찾기
   1. 백트래킹과 결합하여 사용하면 사이클을 감지할 수 있다.
   • [x] 백트래킹이 뭐엿더라
     • 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다가 원하는 값과 불일치 하는 부분이 발생하면 더이상 탐색하지 않고,
     • 전단계로 돌아간다.
   BOJ_15649 : N과 M(1)
   • 사이클 판별 → 동빈나 이코테 8강 ㄱㄱ
4. 미로찾기
   1. 미로에서 출발점~도착점까지의 경로를 찾는 데 사용
5. 문제 해결
   1. 상태 공간 트리에서 특정 상태까지의 경로를 찾는 데 사용된다.
   2. 백트래킹과 조합하여 사용되는 경우가 많다.
   • 상태 공간 트리란?
     • 문제 해결 과정의 중간 상태들을 모두 노드로 구현해놓은 트리
     • leaf node는 해당 문제의 해에 해당되고,
     • 그 들 중 optimum(최적해)가 누구인지 효율적으로 찾아내는 것이 목적
       • 효율적으로 찾아내기 위해 쓰이는 것들이 Brute-Force, Backtracking(Prunning), Branch and Bound
       • backtracking과 branch and bound의 실전적인 차이를 잘 모르겠음.. 문제를 더 풀어봐야아는걸까
6. 그래프 알고리즘
   1. 최소 신장 트리, 강한 연결 요소 찾기, 다익스트라 알고리즘에서 사용된다.

한 경로를 최대한 깊게 파고들기 때문에 최단 경로를 찾지 않는다.

BFS (Breadth-First Search)_너비우선검색

1. 루트 노드에서 시작해 인접한 노드를 먼저 탐색하는 방식으로
2. 시작 정점으로부터 가까운 정점을 먼저 방문하고
   1. 선입선출 방식의 큐(Queue) 자료구조를 활용한다.
      1. 인접한 노드를 반복적으로 큐에 삽입하고
      2. 먼저 삽입된 노드부터 차례로 큐에서 꺼내도록 알고리즘 작성
3. 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법

ex : 미로를 빠져나가는 최단 거리(경로)를 구하는 문제

이걸 구체적인 동작 과정으로 정리하면…

1. 탐색 시작 노드 정보를 큐에 삽입하고 방문처리 한다.
   1. check = [[False]*m for _ in range(n)]
      1. 큐에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크
      2. 탐색한 노드를 재방문하지 않도록 구분하는 것
2. 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문처리한다.
3. 2번의 과정을 더이상 수행할 수 없을때까지 반복한다.
   1. while q: ~
   2. 큐는 선입선출이므로 노드의 레벨 순으로 과정을 수행하게 된다.

from collections import deque

def bfs(graph, start):
	visited = set() 
	queue = deque([start]) 탐색 시작 노드 정보를 큐에 삽입하고 방문처리한다.
	while queue:
		node = queue.popleft() 큐에서 노드를 꺼내
		if node not in visited: 방문하지 않은 인접 노드 정보를
			visited.add(node) 모두 큐에 삽입하고 방문처리한다
			print(node) 노드 방문 시 처리할 작업
			queue.extend(graph[node]-visited) 
			

문제해결을 위해 bfs를 활용하는 알고리즘

1. 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다.
2. 주변 지점 중에서 값이 ‘1’이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문
   1. 새롭게 방문하는 노드까지 최단 거리 값을 기록한다.
3. 방문한 지점에서 다시 상하좌우를 살펴보면서 방문을 진행하는 과정을 반복
   1. 즉, 시작 지점부터 bfs를 수행하여 모든 노드의 최단 거리 값을 기록하는 셈이다.

언제 bfs를 쓸까?

1. 최단 경로 찾기
2. 상태 공간 탐색
   1. 탐색 공간을 나타내는 그래프에서 특정 상태까지의 최단 경로 또는 특정 상태로 도달할 수 있는 모든 경로를 찾는데 사용
3. 그래프 순회
   1. 특정 노드에서 시작하여 그래프의 모든 연결된 컴포넌트를 탐색
4. 네트워크 트래픽 라우팅
5. 게임 알고리즘
   1. 가능한 모든 상태를 탐색하고 최적의 수를 찾을 때
6. 임의의 그래프 문제
   1. 임의의 그래프에서 최단 경로나 특정 조건을 만족하는 노드를 찾는데 사용된다.

---

dfs : 한 노드로부터 인접한 다른 노드를 재귀적으로 방문 처리 한다.
bfs : 큐에 삽입된 순서대로 꺼낸 한 노드로부터 인접한 다른 노드를 큐에 삽입하고 큐가 완전히 빌 때까지 while문으로 반복한다.

---

Reference

https://heytech.tistory.com/56