[Algorithm] BFS, DFS

그래프를 탐색하는 대표적인 방식에는 BFS와 DFS가 있다. 그래프 관련 알고리즘, 동적 프로그래밍 등 다양한 알고리즘 과정에서 응용된 형태로 많이 사용하기 때문에 알고리즘 공부를 할 때에는 필수적으로 알고 있어야 하는 개념이다. 

원래 귀찮아서 글을 안썼는데 알고리즘 시험 범위에 들어가있어서 이번 기회에 정리했다. 

 

BFS (Breadth First Search)

너비우선탐색 : 임의의 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법 
Queue를 이용하여 구현한다. 

 

과정

q와 visitied을 이용해 구현할 것이다.
- q : 다음 방문할 노드를 담아두는 자료구조
- visited : 노드의 방문 여부를 기록해두는 곳 -> visited를 사용하지 않으면 무한 루프에 돌 수 있다. 

1. 시작 정점을 q에 삽입한다.
2. q의 front 값을 꺼낸다. 
3. 꺼낸 노드의 visited = True로 바꾼다.
4. 꺼낸 노드와 이웃한 모든 노드 중 방문하지 않은 노드를 q에 넣는다. 
5. 큐가 소진될 때 까지 2 ~4 과정을 반복한다. 

 

코드 (python)

메모장으로 짠거라 이게 돌아가는 코드인지는 모르겠다. 그냥 참고용으로 봐라.

from collections import deque

deque q


def bfs(graph, n, start): # graph, # of graph, start vertex

	visited = [False for _ in range(n)]
    q.enqueue(start)
    visited[front] = True
    while(!q.empty()):
    	front = q.dequeue()
        print(front)
        for x in graph[front]:
        	if visited[x] == False:
            	visited[x] = True
            	q.enqueue(x)

 

 

교과서 코드 ( 색칠 하는 과정이 추가됨 )

교과서에서는 노드들을 3가지 색상으로 표현하여 설명하고 있다. 

• White : 아무 일도 일어나지 않은 상태의 노드
• Gray : 현재 queue에 들어가있는 노드
• Black : 이미 방문한 노드

 

 

DFS (Depth First Search)

깊이우선탐색 : 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 방식
보통 재귀로 구현한다. 트리 순회가 DFS의 한 방식이다. 

 

코드 (python)

# n : number of vertexes
visited = [False for _ in range(n)]

def dfs(G, v):
	visited[v] = true
    print(v)
    for x in graph[v]:
    	if visited[x] == False:
        	dfs(G, x)

 

교과서 코드 ( 색칠 하는 과정이 추가됨 )

• while : 방문하지 않은 곳
• gray : 방문했고 아직 인접노드를 살피는 중인 노드
• black : 방문한 곳

BFS와 약간 코드 상 차이가 있는게 모든 노드를 방문하기 위한 장치가 하나 더 있다. 물론 BFS도 위와 같은 형식으로 만들어주면 모든 노드를 방문하게 할 수 있지만 일단 교과서 코드로만 이해하면 그렇다. 

 

 

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

간단하게 적용하는 문제니까 한번 풀어보길 바란다.