[Algorithm] BFS(Breadth-First Search)

1. 개요

매일 코딩 테스트 문제를 푸는데 최근 푸는 문제들 중에서 BFS를 써서 해결해야 하는 문제가 많았다. 이전에 한 번 공부한적 있는 내용이긴 하지만 시간이 조금 지나기도 했고, 기억도 잘 나지 않아서 복습도 하고 기록도 해둘 겸 정리글을 써보게 되었다. 무엇보다 그리 자세히 공부를 했던 것 같지는 않아서 이번에 자세히 짚고 넘어가고자 한다.

2. BFS

BFS란?

그래프나 트리에서 루트 노드(혹은 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법

• 현재 노드의 모든 인접한 노드를 방문 ㅡ> 다음 레벨로 이동
• FIFO(선입선출) 특성 때문에 queue를 이용
• 최단 경로 찾기에 활용
• 모든 경로를 한단계씩 탐색
• 노드 방문 여부에 대한 검사가 필요 (안 하면 무한루프 가능성 있음)
• 시간 복잡도 O(V+E) (V: 노드 개수, E: 간선 개수)

BFS 코드

(프로그래머스: https://school.programmers.co.kr/learn/courses/30/lessons/154538 )

#include <string>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

int solution(int x, int y, int n) {
    if (x==y) return 0;
    
    queue<pair<int, int>> q;
    unordered_set<int> visited;
    q.push({y,0});
    visited.insert(y);
    while(!q.empty())
    {
        int cur=q.front().first;
        int count=q.front().second;
        q.pop();
        if(cur==x) return count;
        if(cur-n>=x&&visited.find(cur-n)==visited.end())
        {
            q.push({cur-n,count+1});
            visited.insert(cur-n);
        }
        if(cur%2==0&&visited.find(cur/2)==visited.end())
        {
            q.push({cur/2,count+1});
            visited.insert(cur/2);
        }
        if(cur%3==0&&visited.find(cur/3)==visited.end())
        {
            q.push({cur/3,count+1});
            visited.insert(cur/3);
        }
    }
    return -1;
}

문제를 간단히 설명하자면 x, y, n이 주어졌을 때, 3가지 연산을 통해 y값을 만드는 가장 적은 연산 횟수를 구하는 문제이다.

연산은 다음과 같다.

• x에 n을 더한다
• x에 2를 곱한다
• x에 3을 곱한다

위 3가지 연산을 통해 y값에 도달하는데 가장 적은 연산 횟수를 구하는 문제로 여러 경우의 수를 다 따져봐야 하기 때문에 BFS를 통해 구현하는 것이 적합한 문제이다.

인접한 노드들에 방문했을 때 해당 노드에서의 정보( 현재 값 , 연산 횟수)들을 기억할 필요가 있어 큐를 사용한다. 큐에 현재 값과 연산횟수를 넣어뒀다 다시 빼서 가능한 3가지 연산을 모두 적용해 보기 때문에 그래프나 트리에서 현재 갈 수 있는 인접한 노드들을 전부 탐색하는 형식과 일치한다. 더불어 이미 탐색했던 노드인지를 확인하기 위해 'visited'라는 이름의 unordered_set을 이용하여 빠르게 방문 여부를 체크하는데 이용했다. 

3. 정리

확실히 공부했던 시기가 오래된 알고리즘이었기 때문인지 복습을 하니 기억 안나던 정보들도 기억이 나기 시작했다. 그래프 탐색 관련한 알고리즘들을 구현하는 과제를 진행하면서 구현했던 기억이 있는데 이렇게 다시 공부하기 전까지는 기억이 나지 않았다는 점에서 이전에 배웠던 내용들을 다시 한 번 리마인드하는 시간을 주기적으로 가져야할 필요성이 느껴진다. 코딩 테스트를 풀어보면서 느끼지만 관련한 알고리즘을 알고 있는 문제와 그렇지 못한 문제들에서 푸는데 걸리는 시간 차이가 크기 때문에 코딩 테스트를 해보는 것도 해보는 거지만 알고리즘이나 자료구조 관련한  CS 지식들도 다시 한 번 점검하는 시간을 가져야겠다.

 

---

참고자료

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

https://en.wikipedia.org/wiki/Breadth-first_search

Breadth-first search - Wikipedia