[JAVASCRIPT] 코딩테스트에서 만나는 DFS와 BFS (feat. 큐)

본 포스팅은
책 [코팅 테스트 합격자 되기: 자바스크립트 편 - 이선협, 박경록]
의 내용을 기반으로 작성합니다 ✍️

 

 

이전에 DFS에 대해서는 따로 학습하고 포스팅을 작성한 적이 있지만, 여전히 코딩 테스트에서 만나면 어려움을 겪는다.

어떤 문제를 만났을 때 DFS와 BFS를 활용해야 하는 지를 위주로 조금 더 풀어서 정리하며 이해해본다.

 

 

---

깊이 우선 탐색 (Depth-first Search, DFS)

가장 깊은 노드까지 방문

더 이상 탐색할 노드가 없으면 최근에 방문했던 노드로 되돌아 가, 아직 방문하지 않은 노드를 방문

 

1️⃣ 시작 노드 선정. 스택에 시작 노드를 푸시
스택에 있는 노드는 아직 방문하지 않았지만 방문할 예정인 노드
만일, 스택이 비었다면 이는 방문할 수 있는 모든 노드를 방문했음을 의미. 따라서 스택이 비면 탐색 종료

 

2️⃣ 스택에 노드를 팝
가장 최근에 스택에 푸시한 노드를 팝하는 형식

 

3️⃣ 팝한 노드의 방문 여부를 확인 후 방문 처리
아직 방문하지 않은 노드라면 방문 처리. 이미 방문한 노드라면 별도의 처리 없음

 

4️⃣ 방문한 노드와 인접한 모든 노드 확인
그 중 아직 방문하지 않은 노드를 스택에 푸시

 

 

DFS를 구현 방법은 2가지, 스택과 재귀 함수

스택은 별도의 문자열을 만들어 직접 방문 예정할 노드에 대해서 저장하고 꺼내오는 방식을 사용

재귀 함수는 dfs(N)을 정의하고, 재귀 함수를 호출할 때 마다 호출한 함수 dfs(N)이 콜스택에 쌓이는 것을 활용

 

💡 모든 경우의 수를 찾는 백트래킹 알고리즘을 구현할 때나 그래프의 사이클을 감지해야 하는 경우에 활용

 

 

 

너비 우선 탐색 (Breadth-first Search, BFS)

시작 노드와 거리가 가장 가까운 노드를 우선하여 방문

인접한 노드를 모두 방문한 후 그 다음 단계의 인접 노드를 방문

1️⃣ 시작 노드 선정. 큐에 시작 노드를 푸시
큐에 있는 노드는 이미 방문한 노드
그 노드와 인접한 노드는 아직 탐색하지 않은 상태
만일, 큐가 비었다면 이는 방문할 수 있는 모든 노드를 방문했음을 의미. 따라서 큐가 비면 탐색 종료

 

2️⃣ 큐에 노드를 팝
가장 먼저 큐에 푸시한 노드를 팝하는 형식

 

3️⃣ 팝한 노드의 인접한 모든 노드 확인
그 중 아직 방문하지 않은 노드를 큐에 푸시함으로써 방문 처리

 

 

💡 문제에 대한 답이 많고, 그 중에서도 최적의 답을 구해야하는 경우에 활용

 

 

 

---

예제로 학습하는 DFS

[코딩 테스트 합격자 되기: 자바스크립트 편]의 38번 예제 <깊이 우선 탐색 순회>

 

DFS를 활용하여 방문한 노드를 차례로 출력하는 예제이다.

 

본격적인 DFS 탐색을 진행하기 이전, 먼저 [출발 노드, 도착 노드] 쌍들의 배열인 graph를 연결 리스트로 구현한다.

이 연결 리스트의 형태는 { 노드: [인접 노드, 인접 노드] } 형태가 된다.

function solution(graph, start){
	// 연결 리스트 만들기: key와 인접한 노드의 배열을 value로
	const adjList = {};
	graph.forEach(([u, v]) =>{
		if(!adjList[u]) adjList[u] = [];
		adjList[u].push(v);
	});

	const answer = [];
	return answer;
}

 

 

앞서 언급한 것처럼 DFS는 스택과 재귀함수, 두 가지 방법을 이용해서 풀이할 수 있다.

첫 번째로 재귀함수 dfs()를 만들어 풀이는 아래와 같다.

function solution(graph, start){
	// 연결 리스트 만들기: key와 인접한 노드의 배열을 value로
	const adjList = {};
	graph.forEach(([u, v]) =>{
		if(!adjList[u]) adjList[u] = [];
		adjList[u].push(v);
	});
	
	// dfs 함수: 매개변수로 방문 예정 노드, 방문이 끝난 노드들의 집합, 방문 이력
	function dfs(node, visited, answer){
		visited.add(node); // 방문 처리
		answer.push(node); // 방문 이력에 추가
		(adjList[node] || []).forEach((neighbor) => {
			if(!visited.has(neighbor)) dfs(neighbor, visited, answer);
		});
	}
	
	const visited = new Set();
	const answer = [];
	dfs(start, visited, answer); // 시작점 start를 갖고 콜스택을 쌓기 시작
	return answer;
}

dfs()의 매개변수로 방문 예정 노드, 방문 완료한 노드들의 집합, 방문 이력을 사용한다.

dfs()가 실행될 때 방문 예정이였던 노드를 방문한 것으로 처리해주고, 해당 노드의 인접 노드를 대상으로 dfs()를 다시 한 번 실행한다.

 

 

두 번째로 스택을 만들어 사용하는 방법이다.

function solution(graph, start){
	// 연결 리스트 만들기: key와 인접한 노드의 배열을 value로
	const adjList = {};
	graph.forEach(([u, v]) =>{
		if(!adjList[u]) adjList[u] = [];
		adjList[u].push(v);
	});
	
	const stack = [start]; // 방문 예정 노드를 스택에 넣어 관리. 시작점을 넣고 시작
	const visited = new Set();
	const answer = [];
	while(stack.length > 0){ // 스택이 비면 탐색 종료
		const node = stack.pop();
		if(!visited.has(node)) {
			visited.add(node);
			answer.push(node);
			(adjList[node] || []).forEach((neighbor) => {
				if(!visited.has(neighbor)) stack.push(neighbor);
			});
		}
	}
	return answer;
}

방문 예정인 노드를 stack에 넣음으로써 관리한다. 이 stack의 길이가 0이 될 때까지 탐색을 진행한다.

 

 

 

예제로 학습하는 BFS

[코딩 테스트 합격자 되기: 자바스크립트 편]의 39번 예제 <너비 우선 탐색 순회>

 

BFS를 활용하여 방문한 노드를 차례로 출력하는 예제이다.

앞서 했던 것과 동일하게 연결 리스트를 구현하고 시작한다.

function solution(graph, start){
	// 연결 리스트 만들기: key와 인접한 노드의 배열을 value로
	const adjList = {};
	graph.forEach(([u, v]) =>{
		if(!adjList[u]) adjList[u] = [];
		adjList[u].push(v);
	});

	const answer = [];
	return answer;
}

 

 

DFS의 경우 큐를 사용해서 풀이한다.

이 때 배열에서 shift() 연산을 사용해서 큐의 후입선출을 구현할 수 있지만, shift()의 경우는 배열의 모든 인덱스를 수정하기 때문에 시간 복잡도 면에서 비효율적인 메소드이다. 때문에 class를 이용해 큐를 직접 구현하고, shift() 사용 대신 index를 활용해서 조금 더 효율을 챙길 수 있다. 아래처럼 큐를 직접 구현한다.

class Queue {
	items = [];
	front = 0;
	rear = 0;
	push(item) {
		this.items.push(item);
		this.rear++;
	}
	pop() {
		return this.items[this.front++];
	}
	isEmpty() {
		return this.rear === this.front;
	}
}

 

그리고 스택을 활용한 DFS 구현과 유사한 구조로 BFS를 구현한다.

여기에서 주의해야 할 부분. DFS의 경우는 스택에 방문 예정인 노드를 넣고 pop할 때 방문 처리를 했는데, BFS의 경우는 큐에 방문 예정인 노드를 넣음과 동시에 방문 처리를 진행한다는 점을 유의해서 구현한다.

function solution(graph, start){
	// 연결 리스트 만들기: key와 인접한 노드의 배열을 value로
	const adjList = {};
	graph.forEach(([u, v]) =>{
		if(!adjList[u]) adjList[u] = [];
		adjList[u].push(v);
	});
	
	const queue = new Queue(); // 인접 노드를 저장할 큐
	const visited = new Set();
	queue.push(start);
	visited.add(start); // BFS는 큐에 넣는 즉시 방문한 것으로 처리
	const answer = [start];
	
	while(!queue.isEmpty()){
		const node = queue.pop();
		(adjList[node] || []).forEach((neighbor) => {
			if(!visited.has(neighbor)){
				queue.push(neighbor);
				visited.add(neighbor);
				answer.push(neighbor);
			}
		});
	}
	return answer;
}