[알고리즘] DFS/ BFS

● 자료구조 스택 & 큐

 

1. 스택 : 선입 수출의 구조를 갖는 자료구조

 

- 박스 쌓기에 비유할 수 있다. 마지막에 쌓은 박스를 먼저 꺼내야 아래 박스를 꺼낼 수 있다.

 

- 일반적인 리스트 구조가 스택에 해당된다. (스택을 이용한 알고리즘을 사용할 때 일반 리스트 사용)

 

- 입력(append), 출력(pop) 사용. 

 

2. 큐 : 선입선출의 구조를 갖는 자료구조

 

- 대기줄처럼 먼저 들어온 데이터를 먼저 출력한다.

 

- 라이브러리 collections에서 deque로 사용 가능하다.

 

- 입력(append), 출력(popleft) 사용.

 

 

● DFS / BFS

 

1. DFS 깊이 우선 탐색 : 그래프에서 가장 깊은 곳을 먼저 탐색하는 방법

그래프

- 1번부터 인접한 노드를  DFS로 탐색하는 과정

1번을 방문, 왼쪽 자료구조에 방문 표시 // 1번과 연결된 노드 중 2번 방문

2번과 연결된 7번을 방문 // 7번과 연결된 6번을 방문

6번과 연결된 노드 중 방문하지 않은 노드가 존재하지 않기 때문에 자료구조에서 6을 출력하여 7로 돌아간 후 8번 방문

- 위 과정을 반복하여 전체 노드를 방문(1 2 7 6 8 3 4 5 순서)

 

- 코드로 구현

#graph 노드의 연결관계 [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
#v 현재 노드 번호
#visited 방문 표시 [False] * 9

def dfs(graph,v,visited):
  
  visited[v] = True # 현재 노드 방문표시
  
  print(v,end=' ')
  
  for i in graph[v]: # 연결된 노드 중에 방문하지 않은 노드가 있다면 방문
  
  	if not visited[i]:
  
  		dfs(graph,i,visited) # DFS는 재귀함수를 이용한다.

 

● BFS 너비 우선 탐색 : 그래프에서 주변부터 탐색하는 방법

 

- 1번 노드부터 BFS로 탐색하는 과정(위 예시)

1번 노드를 방문, 왼쪽 자료구조(큐)에 방문 표시 // 1번과 연결된 주변 노드 방문(1을 출력)

2번을 출력(1번 다음으로 입력된 값)하고 2번 주변의 노드 방문

- 위 과정을 반복하여 전체 노트 탐색(1 2 3 8 7 4 5 6 순서)

 

- 코드로 구현

from collections import deque

def bfs(graph, start, visited):
  queue = deque([start])

  visited[start] = True

  while queue: # 큐가 빌 때 까지

    v = queue.popleft() # 현재 노드를 빼야 다음으로 넘어감
    
    print(v,end=' ')
    
    for i in graph[v]:
    
    	if not visited[i]:  
    
    		queue.append(i)
    
    		visited[i] = True