dfs와 bfs

그래프 탐색 알고리즘 : dfs/bfs

1. 탐색(search)

   • 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

2. 그래프(graph)

   • 노드(node)와 간선(edge)으로 표현되며 이때 노드를 정점이라고 한다

3. 그래프 탐색

   • 하나의 노드를 시작으로 다수의 노드를 방문하는 것

4. 대표적인 그래프 탐색 알고리즘

   • dfs와 bfs가 있음

dfs/bfs를 알기 전에 알아두어야 할 자료구조

스택(stack)

1. 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
2. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있음
3. 스택 구현 예제
   

	# 스택 구현을 위해 파이썬의 기본 자료형인 리스트를 활용
    stack = []
        
    # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
    stack.append(5)
    stack.append(2)
    stack.append(3)
    stack.append(7)
    stack.pop()
    stack.append(1)
    stack.append(4)
    stack.pop()
        
    print(stack) #1-3-2-5
    print(stack[::-1]) #5-2-3-1

큐(queue)

1. 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
2. 입구와 출구가 모두 뚫려있는 터널과 같은 형태로 시각화 할 수 있음
3. 큐 구현 예제
   

    from collections import deque
        
    # 큐 구현을 위해 파이썬의 deque 라이브러리 활용
    queue = deque()
        
    # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
    queue.append(5)
    queue.append(2)
    queue.append(3)
    queue.append(7)
    queue.popleft()
    queue.append(1)
    queue.append(4)
    queue.popleft()
        
    print(queue) #3-7-1-4
    queue.reverse() #역순으로 변환
    print(queue) #4-1-7-3

*c++은 queue 자료구조 사용. append() 대신 push(), popleft() 대신 pop(), 단순 추출은 front()

*java도 queue 자료구조 사용. append() 대신 offer(), popleft() 대신 poll()

재귀함수

1. 자기 자신을 다시 호출하는 함수
2. 재귀함수를 문제 풀이에 이용할 때에는 재귀 함수의 종료조건을 반드시 명시해야함
3. 종료조건을 제대로 명시하지 않으면 함수가 무한히 출력될 수 있음
4. 예제1 - 팩토리얼
   

        def factorial(n):
        	if n==1: # 또는 n<=1
        		return 1
        	return n * factorial(n-1)
        
        factorial(6) #6!=6*5*4*3*2*1

5. 예제2 - 최대공약수 계산 (유클리드 호제법)

• 유클리드 호제법

  두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 정의하였을 때, A와 B의 최대공약수는 R과 B의 최대공약수와 같음.

  ex. GCD(192, 162)

        def gcd(a,b):
        	if a%b == 0 :
        		return b
        	return gcd(b,a%b)

6. 재귀함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있음
7. 모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있음
8. 컴퓨터가 함수를 연속으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓이게 됨
   • 그래서 스택을 사용해야할 때 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많음

DFS (Depth-First Search)

1. DFS는 깊이 우선 탐색이라고도 불리며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

2. DFS는 스택 알고리즘 또는 재귀함수를 이용하며, 구체적인 동작과정은 아래와 같음

   ➡️ 동작 과정

   1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 함
   2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문처리하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
   3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

3. dfs 구현 예제

    def dfs(graph, v, visited):
    	visited[v]=True # 방문처리
    	print(v,end='')
    	# 현재 노드와 인접한 노드들을 재귀적으로 방문
    	for i in graph[v]:
    		if not visited[i]:
    			dfs(graph,i,visited)
    
    # 각 노드가 연결된 정보를 표현 (2차원 리스트)
    graph=[
    	[],
    	[2,3,8],
    	[1,7],
    	[1,4,5],
    	[3,5],
    	[3,4],
    	[7],
    	[2,6,8],
    	[1,7],
    ]
    
    # 각 노드가 방문된 정보를 표현 (1차원 리스트)
    visited = [False]*9
    
    # 정의된 dfs 호출
    dfs(graph,1,visited)

BFS (Breadth-First Search)

1. BFS는 너비 우선 탐색이라고도 불리며, 그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘
2. BFS는 큐 자료구조를 사용하며, 동작 과정은 아래와 같음

   ➡️ 동작 과정

   1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 함
   2. 큐에서 노드를 꺼낸뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
   3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

3. bfs 구현예제

    from collections import deque
    
    def bfs(graph, start, visited):
    	queue = deque([start])
    	visited[start]=True
    
    	# queue가 빌 때까지 반복
    	while queue:
    		v= queue.popleft()
    		# 현재 노드와 인접한 노드들을 모두 방문
    		for i in graph[v]:
    			if not visited[i]:
    				queue.append(i)
    				visited[i]=True
    				
    
    # 각 노드가 연결된 정보를 표현 (2차원 리스트)
    graph=[
    	[],
    	[2,3,8],
    	[1,7],
    	[1,4,5],
    	[3,5],
    	[3,4],
    	[7],
    	[2,6,8],
    	[1,7],
    ]
    
    # 각 노드가 방문된 정보를 표현 (1차원 리스트)
    visited = [False]*9
    
    # 정의된 dfs 호출
    dfs(graph,1,visited)