[알고리즘] BFS

📌 알고리즘 기초 이론

1. 시간 복잡도

• 알고리즘의 성능을 나타내는 척도
• 특정한 크기의 입력에 대하여 알고리즘 수행 시간 분석
• 동일한 기능에 시간 복잡도가 낮을수록 우수

    2. 빅오 표기법

• 가장 빠르게 증가하는 항만을 고려하는 표기법
• 차수가 가장 큰 항에서 계수를 제외하여 표현
• ex) 연산 횟수가 아래와 같은 알고리즘의 빅오로 표시하면?

 3N^3 + 5N^2 + 1000000 → O(N^3) 

 

    3. 예시 ( N=5의 케이스)

 

let arr = [3, 5, 1, 2, 4];
let sum = 0;

for (let i=0; i<arr.length; i++) {
	sum += arr[i];
}

console.log(sum);

• 수행 시간은 데이터 개수 N에 비례, 시간 복잡도: O(N)

1. Q1. N개의 데이터 합을 계산하는 프로그램

Q2. 이중 반복문 예제

let arr = [3, 5, 1, 2, 4];
for (let i=0; i<arr.length; i++) {
	for (let j=0; j<arr.length; j++) {
		let tmp = arr[i] * arr[j];
		console.log(tmp);
	}
}

• 시간 복잡도: O(N²)

    4. 알고리즘 설계 시 시간 제한별 고려사항 (시간 제한이 1초인 문제)N의 범위 시간복잡도

500	O(N³)
2000	O(N²)
10000	O(NlogN)
10000000	O(N)

📌유형 스터디

💡 BFS 너비 우선 탐색

 

• 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다
• BFS는 재귀적으로 동작하지 않는다.
• 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다. 즉, 선입선출(FIFO) 원칙으로 탐색 https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

 💡 Queue

 

class Queue {
    constructor() {
        this.items = {};
        this.headIndex = 0;
        this.tailIndex = 0;
    }

    enqueue(item) {
        this.items[this.tailIndex] = item;
        this.tailIndex++;
    }

    dequeue() {
        const item = this.items[this.headIndex];
        delete this.items[this.headIndex];
        this.headIndex++;
        return item;
    }
    
    peek() {
        return this.items[this.headIndex];
    }

    getLength() {
        return this.tailIndex - this.headIndex;
    }

}

💡 기본 동작 방식

 

1. 시작 노드를 큐에 넣고 방문 처리
2. 큐에서 원소를 꺼내어 (dequeue) 방문하지 않은 인접 노드가 있는지 확인
3. 있다면 방문하지 않은 인접 노드를 큐에 모두 삽입하고 방문 처리
4. 2번 과정을 더 이상 반복할 수 없을 때까지 반복

💡 사용 예시

 

1. 간선 비용이 동일할 때 최단 거리 문제를 해결하는 경우
2. 완전 탐색을 위해 사용한 DFS 솔루션이 메모리/시간 초과를 받아 BFS로 재시도 하는 경우

💡 예제

 

import { Queue } from "../../algorithm/bfs/index.js";
let graph = [
    [],
    [2, 3, 4],
    [1],
    [1, 5, 6],
    [1, 7],
    [3, 8],
    [3],
    [4],
    [5]
];

let visited = new Array(9).fill(false);
bfs(graph, 1, visited);

function bfs(graph, start, visited) {

    let queue = new Queue();
    queue.enqueue(start);
    visited[start] = true;

    while (queue.getLength() != 0) {
        let cur = queue.dequeue();
        console.log(cur);
        for (let i of graph[cur]) {
            if (!visited[i]) {
                queue.enqueue(i);
                visited[i] = true;
            }
        }
    }
}