[CS 면접 대비] DFS/BFS 개념 & 파이썬 코드 정리

 

DFS란?

; Depth First Search, 깊이 우선 탐색

: 그래프에서 깊은 곳을 먼저 탐색하는 알고리즘

 

DFS 알고리즘 이해를 위해서는 스택과 그래프 자료구조에 대한 이해가 필요합니다.

 

↓ ↓ ↓

 

1) 스택이란?

: 스택은 후입 선출 (LIFO, 한쪽에서만 데이터를 넣고 뺄수 있음) 

★ 재귀 함수와 스택 자료구조가 동일하기때문에 스택이 DFS에 쓰인다.

: 재귀함수에서는 동일한 함수를 호출할 때마다 함수를 위한 메모리가 계속해서 할당된다. 이때 사용되는 메모리가 스택!

스택은 후입선출 구조이기 때문에 가장 마지막에 호출된 함수 factorial(1)을 먼저 완료하고, 값을 아래로 전달하여 최초로 호출된 함수 factorial(3)이 최종 값을 계산한다.

 

2) 그래프란?

: 그래프는 노드(정점)와 간선으로 표현됩니다. 

 

그래프는 2가지 방식으로 표현 가능합니다.

 

1) 인접 행렬 : 2차원 배열로 그래프 연결관계 표현, 모든 관계 저장하여 메모리 낭비

그래프, 인접행렬

2) 인접 리스트 : 리스트로 그래프 연결관계 표현, 연결정보만 저장하여 메모리 효율적으로 사용

★ DFS 동작 과정

1) 탐색 시작 노드 스택에 삽입, 방문처리

2) 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리.

> 모두 방문 처리가 된 경우는 스택에서 다음 최상단 노드를 꺼냄

3) 2번을 더 이상 수행할 수 없을 때까지 반복함

 

def dfs(graph, v, visited):
	visited[v] = True # (1)
    
    print(v, end=' ') 
    for i in graph[v]: # (2)
    	if not visited[i]:
        	dfs(graph, i, visited) # 재귀, 가장 깊숙한 곳까지 방문

 

---

BFS란?

; Bread First Search, 너비 우선 탐색

: 그래프에서 가까운 곳을 먼저 탐색하는 알고리즘

 

BFS 알고리즘 이해를 위해서는 큐와 그래프 자료구조에 대한 이해가 필요합니다.

 

↓ ↓ ↓

 

큐(Queue)란?

: 큐는 선입선출, 편의점 물건 진열과 같음(먼저 온 물건 빨리 팔기)

 

★ BFS 동작 과정

1) 탐색 시작할 노드 큐에 삽입, 방문처리

2) 큐에서 노드 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드 모드 큐에 삽입하고 방문처리

3) 2번을 더 이상 수행할 수 없을 때까지 반복함

 

from collections import deque

visited = [False]*9

def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    
    while queue:
    	v = queue.popleft()
        print(v)
        for i in graph[v]:
        	queue.append(i)
            visited[i]=True