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

BFS는 그래프나 트리 구조에서 노드를 탐색하는 알고리즘으로, 루트 노드(혹은 시작 노드)에서 시작하여 인접한 노드들을 먼저 탐색하는 방식이다.

 

주요 특징:

1. 큐(Queue) 자료구조를 사용
2. 같은 레벨(depth)에 있는 노드들을 먼저 탐색
3. 최단 경로를 찾는 문제에서 많이 사용됨

BFS의 실제 활용 사례:

1. 최단 경로 찾기 (예: 네비게이션)
2. 웹 크롤링
3. SNS에서 친구 추천 시스템
4. 네트워크 탐색

아래 코드는 A 노드에서 출발하여 BFS를 하는 과정을 출력한다.

// 그래프를 인접 리스트로 표현
const graph = {
    A: ['B', 'C'],
    B: ['A', 'D', 'E'],
    C: ['A', 'F'],
    D: ['B'],
    E: ['B', 'F'],
    F: ['C', 'E']
};

function bfs(graph, startNode) {
    const visited = new Set(); // 방문한 노드를 저장하는 Set. 빈 객체로 선언하기도 함.
    const queue = [startNode];  // 탐색할 노드를 저장하는 큐. 빈 배열로 선언하고 .push(startNode)하여 따로 넣어주기도 함.
    
    visited.add(startNode);
    
    while (queue.length > 0) {
        const currentNode = queue.shift(); // 큐에서 노드를 꺼냄
        console.log(currentNode); // 현재 노드 출력
        
        // 인접한 노드들을 확인
        for (const neighbor of graph[currentNode]) {
            if (!visited.has(neighbor)) { // 방문하지 않은 노드라면
                visited.add(neighbor);    // 방문 처리
                queue.push(neighbor);     // 큐에 추가
            }
        }
    }
}

// 사용 예시
bfs(graph, 'A');


/*
A (시작 노드)
B, C (A의 이웃 노드들)
D, E, F (B와 C의 이웃 노드들)

: 위 순서대로 방문함
*/

 

 

이를 응용하여 아래와 같이 최단거리를 구할 수도 있다.

const graph = {
    A: ['B', 'C'],
    B: ['A', 'D'],
    C: ['A', 'E', 'F'],
    D: ['B'],
    E: ['C'],
    F: ['C', 'E'],
    G: ['E', 'H'],
    H: ['G']
};

const bfs = (graph, startNode, targetNode) => {
    const visited = {}; // 방문할 노드를 저장할 객체
    const queue = [];   // 탐색 예정인 노드들의 대기열인 큐
    const distances = {};   // 시작 노드부터의 거리를 저장할 객체

    visited[startNode] = true;  // 시작 노드를 방문처리
    queue.push(startNode);  // 시작 노드를 큐에 추가.
    distances[startNode] = 0;   // 시작노드에서 시작노드까지의 거리를 0으로 지정

    while(queue.length > 0) {
        const node = queue.shift(); // 큐의 맨 앞에 존재하는 원소를 제거하면서 할당

        if(node === targetNode) {
            return distances[targetNode];   // 목표 정점에 도달한 경우 거리 반환
        }

        const adjacentNodes = graph[node];   // 인접 노드들을 가져옴
        for( let i = 0; i < adjacentNodes.length; i++) {
            const adjacentNode = adjacentNodes[i];
            if(!visited[adjacentNode]) {    // 미방문 노드인 경우 
                visited[adjacentNode] = true;   // 방문처리
                queue.push(adjacentNode)    // 큐에 추가
                distances[adjacentNode] = distances[node] + 1   // 거리 업데이트
            }
        }
    }
    return -1;  // 탐색 실패 시 -1 반환
}

// 최단거리 계산 호출 예시
const shortestDistances = bfs(graph, 'A', 'E')
console.log(`A에서 E까지의 최단거리: ${shortestDistances}`)	// 2	(A -> C -> E)

 

/*
가장 좋아하는 연예인 소개 받기
한국인 배열에서, 이소영이 최인기를 찾는 방법
*/

const korean = [
    {
        이름: "이소영",
        주민등록번호: "990825-2305941",
        친구: ["990412-1450372", "970501-2295043"]
    },
    {
        이름: "김민수",
        주민등록번호: "990412-1450372",
        친구: ["990825-2305941", "850410-1234567", "970501-2295043"]
    },
        /*... */

    {
        이름: "박지은",
        주민등록번호: "970501-2295043",
        친구: ["990825-2305941", "850410-1234567"]
    },
    {
        이름: "최인기",
        주민등록번호: "850410-1234567",  // 찾고자 하는 생일을 가진 사람
        친구: ["990412-1450372", "970501-2295043"]
    }
];



function findFriendOfFriendBFS(name, targetBirthdate) {

    const visited = new Set();
    const queue = [];

    // 이소영을 큐에 추가
    queue.push(
        {   //  파라미터 name과 같은 이름을 가진 객체 반환. 따라서 person 속성엔 객체가 값으로 저장된다.
            person: korean.find(person => person.이름 === name), 
            depth: 0 
        }
    )

    while(queue.length !== 0) {
        const {person, depth} = queue.shift();

        if (person) {
            // 현재 사용자의 친구 목록을 확인
            for (const friendId of person.친구) {
                const friend = korean.find(p => p.주민등록번호 === friendId);

                if (friend && !visited.has(friendId)) {
                    visited.add(friendId);

                    // 생일을 기준으로 최인기 찾기
                    if(friend.주민등록번호.startsWith(targetBirthdate)) {
                        return {
                            찾은사람: friend,
                            거리: depth + 1
                        };
                    }

                    // 친구의 친구를 큐에 추가
                    queue.push(
                        {
                            person: friend,
                            depth: depth + 1
                        }
                    )
                }
            }
        }
    }

    return null // 찾지 못한 경우
}

//  이소영의 친구의 친구 중 생일이 1985년 4월 10일인 사용자 찾기
const resultBFS = findFriendOfFriendBFS("이소영", "850410");
console.log(resultBFS);
/*

{
  '찾은사람': {
    '이름': '최인기',
    '주민등록번호': '850410-1234567',
    '친구': [ '990412-1450372', '970501-2295043' ]
  },
  '거리': 2	// 김민수 -> 최인기
}

*/

 

 

 

 

그러나 단순 최단경로를 구하는 것이 아니고 모든 경우의 수를 고려해야 한다면 외판원 문제(Traveling Salesman Problem, TPS)를 적용해야 할 수도 있다. 최단경로라고 해서 BFS만을 떠올리면 안되는 이유이다.