[ ᴀʟɢᴏʀɪᴛʜᴍ ] Graph Traversal ( 그래프 순회 ) - BFS & DFS

NewHa·2023년 9월 19일
algorithm
0

ᴀʟɢᴏʀɪᴛʜᴍ

목록 보기
15/19
post-thumbnail

그래프(Graph)

그래프는 노드(Node)와 간선(Edge)로 구성된 자료구조입니다. 여러 개의 점이 선으로 연결되어 있는 구조로, 간선에 방향이 있으면 방향 그래프, 방향이 없으면 양방향 그래프라고 합니다.

🔗

그래프에 관한 더 자세한 내용은 다음 게시글을 참고해주세요.

그래프 탐색

그래프 탐색(순회)란 그래프 내의 모든 노드를 한 번씩 방문하여 살펴보는 것을 말합니다.

현실 세계의 많은 것들을 그래프 형태로 표현할 수 있습니다. 가장 쉽게 볼 수 있는 예가 ‘지하철 노선도’입니다. 각각의 역들(Node)이 간선으로 이어져있습니다. 우리는 도착지까지 최단 거리, 최소 환승 등에 따라 경로를 찾습니다. 이 때 그래프 탐색을 사용해서 경로를 찾을 수 있습니다.

그래프 탐색 알고리즘으로는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS), 두 가지 방식이 존재합니다. 두 알고리즘 모두 모든 노드를 방문하므로 시간복잡도는 O(노드수 + 간선수)입니다.

일반적인 그래프 탐색 문제에서는 깊이 우선 탐색과 너비 우선 탐색 모두 사용 가능합니다. 만약 문제가 시작 노드로부터 가까운 노드 순으로 방문해야 하는 경우에는 너비 우선 탐색으로 구현해야합니다.

그래프 탐색은 차후 다익스트라 알고리즘, 크루스칼/프림 알고리즘, 위상 정렬과 같은 다른 알고리즘의 기반이 됩니다.

DFS는 한 방향으로 갈 수 있을 때까지 깊게 내려갔다가, 더 이상 갈 곳이 없으면 돌아와서 다른 방향을 탐색하는 방식의 그래프 탐색 알고리즘입니다. 즉 현재 탐색 중인 노드를 기준으로 해당 노드에 연결된 노드들을 타고 최대한 쭉 내려가서, 깊이를 우선으로 탐색하여 깊이 우선 탐색이라고 부릅니다.

DFS는 예를 들면 미로 길찾기와 같습니다. 갈 수 있는 곳을 따라 계속 앞으로 전진하다가 벽을 만나면 다시 되돌아와서 다른 갈래의 길로 다시 전진하는 것과 같습니다. 그러한 과정을 반복하며 모든 길을 찾는 것입니다.

아래 예시를 통해 자세하게 알아보겠습니다.

  • 1번 노드를 시작 노드로 합니다. 1번 노드를 방문하고 방문표시를 남깁니다.
    • 1번 노드와 연결된 2번 노드를 방문하고 방문표시를 남깁니다.
      • 2번 노드와 연결된 5번 노드를 방문하고 방문표시를 남깁니다.
        • 5번 노드와 연결된 3번 노드르 방문하고 방문표시를 남깁니다.
  • 3번 노드와 연결된 1번 노드를 방문하지만, 방문표시가 되어 있으므로 1과 연결된 다른 간선으로 이동합니다.
    • 1번 노드와 연결된 4번 노드를 방문하고 방문표시를 남깁니다.
      • 4번 노드와 연결된 6번 노드를 방문하고 방문표시를 남깁니다.
    • 더이상 연결된 노드가 없으므로 4번 노드로 돌아가지만, 방문 표시가 되어 있으므로 4와 연결된 다른 간선을 통해 7번 노드를 방문하고 방문표시를 남깁니다.
      • 7번 노드와 연결된 8번 노드를 방문하고 방문표시를 남깁니다.
  • 더 이상 연결된 노드가 없으므로 백트래킹으로 되돌아가서 시작 노드인 1번 노드로 돌아가지만 다른 갈래가 없으므로 탐색을 종료합니다.

만약 예시와 다르게 연결되지 않은 그래프라면 모든 정점에 대해 DFS를 한 번씩 호출해서 모든 노드를 탐색해야합니다.

정리하자면, DFS는 다음 원리에 따라 구현합니다.

  1. 시작 노드를 방문하고, 이미 방문한 노드는 다시 방문하지 않도록 방문처리를 합니다.
  2. 연결된 노드 중 아직 방문하지 않은 노드를 재귀적으로 방문합니다.
  3. 더 이상 방문할 노드가 없으면 이전 단게로 돌아가 다른 갈래를 탐색합니다. 이를 백트래킹(backtracking)이라하고 DFS의 핵심 동작 원리입니다.
  4. 이러한 과정을 반복해 그래프 전체를 탐색합니다.

1️⃣ 재귀를 이용한 DFS 구현 코드

가장 일반적이고 직관적인 방법입니다. 현재 노드를 방문하고 방문목록에 표시하고, 연결된 노드를 재귀함수로 호출해서 탐색합니다. 

// 예시의 그래프는 다음과 같습니다.
const graph = {
  1: [2, 3, 4],
  2: [1, 5],
  3: [1, 5],
  4: [1, 6],
  5: [2, 3],
  6: [4, 7],
  7: [6, 8],
  8: [7],
};
const visited = new Set();

// 시작 노드를 정해줍니다.
function DFS(start){
	// 방문목록에 있는 node면 종료합니다.
	if(visited.has(start)) return;
	// 아니라면 해당 노드를 출력하고 방문목록에 추가합니다.
	console.log(start);
	visited.add(start);
	
	// 해당 노드에 연결된 노드를 순회하면서
	for(const next of graph[start]) {
		// 방문 목록에 없는 노드라면
		if(!visitied.has(next) {
			// 재귀적으로 DFS를 호출합니다.
			DFS(next)
		}
	}
}

DFS(1); // 1 → 2 → 5 → 3 → 4 → 6 → 7 → 8 순으로 출력됩니다.

2️⃣ 스택을 이용한 DFS 구현 코드

재귀 대신 스택을 사용하여 반복문으로도 구현할 수 있습니다. Node.js에서는 재귀적으로 DFS를 호출하는 경우 stack overflow로 에러가 발생할 수 있습니다. 이 때, 스택을 사용해서 이를 방지할 수 있습니다.

하지만, 상대적으로 구현이 복잡하고 순서를 제어해야 합니다.

const visited = new Set();

function DFS(start) {
	// 시작 노드를 스택에 추가합니다.
	const stack = [start];
	
	while(stack.length > 0) {
		// 가장 마지막에 넣은 노드를 꺼냅니다.
		const node = stack.pop();
	
		// 방문목록에 없는 노드라면 출력하고 방문목록에 추가합니다.
		if(!visited.has(node)) {
			console.log(node);
			visited.add(node);
			
			// 연결된 노드를 택에 넣고 역순으로 push합니다.
			for(let i = graph[node].length - 1; i >= 0; i--) {
				const next = graph[node][i];
				if(!visited.has(node)) {
					stack.push(next)
				}
			}
		}
	}
}

DFS(1); // 1 → 2 → 5 → 3 → 4 → 6 → 7 → 8 순으로 출력됩니다.

BFS는 시작 노드를 기준으로 거리가 가까운 노드부터 하나씩 넓게 탐색하는 방식의 그래프 탐색 알고리즘입니다. 큐(Queue)를 사용해 현재 위치에서 인접한 모든 노드를 먼저 탐색한 후, 그 다음 깊이로 진행합니다.

같은 그래프 예시를 통해 알아보겠습니다.

  • 1번 노드를 시작노드로 합니다. 1번 노드를 큐에 넣고 방문표시를 합니다.
  • 큐에서 1번 노드를 꺼냅니다.
    • 1번 노드와 연결된 2번 노드를 방문하고 방문표시가 없으므로 2번 노드를 큐에 넣고 방문표시를 합니다.
    • 1번 노드와 연결된 3번 노드를 방문하고 방문표시가 없으므로 3번 노드를 큐에 넣고 방문표시를 합니다.
    • 1번 노드와 연결된 4번 노드를 방문하고 방문표시가 없으므로 4번 노드를 큐에 넣고 방문표시를 합니다.
  • 더이상 1번 노드에 연결된 노드가 없으므로 큐에서 다음 노드인 2번 노드를 꺼냅니다.
    • 2번 노드와 연결된 1번 노드를 방문합니다. 방문 표시가 있으므로 넘어갑니다.
    • 2번 노드와 연결된 5번 노드를 방문합니다. 방문표시가 없으므로 5번 노드를 큐에 넣고 방문표시를 합니다.
  • 더 이상 2번 노드에 연결된 노드가 없으므로 큐에서 다음 노드인 3번 노드를 꺼냅니다.
    • 3번 노드와 연결된 1번 노드를 방문합니다. 방문 표시가 있으므로 넘어갑니다.
    • 3번 노드와 연결된 5번 노드를 방문합니다. 방문 표시가 있으므로 넘어갑니다.
  • 더 이상 3번 노드에 연결된 노드가 없으므로 큐에서 다음 노드인 4번 노드를 꺼냅니다.
    • 4번 노드와 연결된 1번 노드를 방문합니다. 방문 표시가 있으므로 넘어갑니다.
    • 4번 노드와 연결된 6번 노드를 방문합니다. 방문표시가 없으므로 6번 노드를 큐에 넣고 방문표시를 합니다.
    • 4번 노드와 연결된 7번 노드를 방문합니다. 방문표시가 없으므로 7번 노드를 큐에 넣고 방문표시를 합니다.
  • 더 이상 4번 노드에 연결된 노드가 없으므로 큐에서 다음 노드인 5번 노드를 꺼냅니다.
    • 5번 노드와 연결된 2번 노드를 방문합니다. 방문 표시가 있으므로 넘어갑니다.
    • 5번 노드와 연결된 3번 노드를 방문합니다. 방문 표시가 있으므로 넘어갑니다.
  • 더이상 5번 노드에 연결된 노드가 없으므로 큐에서 다음 노드인 6번 노드를 꺼냅니다.
    • 6번 노드와 연결된 4번 노드를 방문합니다. 방문 표시가 있으므로 넘어갑니다.
  • 더이상 6번 노드에 연결된 노드가 없으므로 큐에서 다음 노드인 7번 노드를 꺼냅니다.
    • 7번 노드와 연결된 4번 노드를 방문합니다. 방문 표시가 있으므로 넘어갑니다.
    • 7번 노드와 연결된 8번 노드를 방문합니다. 방문표시가 없으므로 8번 노드를 큐에 넣고 방문표시를 합니다.
  • 더이상 7번 노드에 연결된 노드가 없으므로 큐에서 다음 노드인 8번 노드를 꺼냅니다.
    • 8번 노드와 연결된 7번 노드를 방문합니다. 방문 표시가 있으므로 넘어값니다.
  • 탐색을 종료합니다.

정리하자면 BFS는 다음 원리에 따라 구현합니다.

  1. 시작 노드를 큐에 넣고 방문처리합니다.
  2. 큐에서 노드를 하나씩 꺼내어 그 노드와 연결된 모든 노드를 큐에 추가하고 방문처리 합니다.
  3. 큐가 빌 때까지 반복하여 탐색합니다.

🚀 BFS 구현 코드

const visited = new Set();

function BFS(start) {
	// 큐에 시작 노드를 넣어주고, 방문표시를 합니다.
	const queue = [start];
	visited.add(start);
	
	// 큐가 빌 때까지 반복합니다.
	while(queue.length > 0) {
		// 큐에서 노드를 꺼내어 출력합니다.
		const node = queue.shift();
		console.log(node);
		
		// 해당 노드에 연결된 노드를 순회합니다.
		for(const next of graph[node]){
			// 연결된 노드가 방문목록에 없으면 큐에 추가하고 방문표시를 합니다.
			if(!visited.has(next)) {
				queue.push(next);
				visited.add(next);
			}
		}
	}
}

BFS(1); // 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 순으로 출력됩니다.

DFS vs BFS 비교 정리

💡 그래프 순회 코딩테스트 문제 풀이

profile
NewHa
백 번을 보면 한 가지는 안다 👀
이전 포스트

[ ᴀʟɢᴏʀɪᴛʜᴍ ] Graph Data Structure( 그래프 )

다음 포스트

[ ᴀʟɢᴏʀɪᴛʜᴍ ] Heap ( 힙 ) & Priority Queue ( 우선순위 큐 )

0개의 댓글