BFS 예시 코드 [C++, Python]

큐를 활용해 너비 우선 탐색을 시행하는 예시 코드이다.

 

C++ - Flood Fill BFS

// BFS 예시 코드

#include <bits/stdc++.h>
using namespace std;

int board[502][502];
bool vis[502][502];
int n = 7, m = 10; // n은 가로 길이, m은 세로 길이
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    queue<pair<int, int>> Q;
    vis[0][0] = true;
    Q.push(make_pair(0, 0));

    while(!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();
        cout << '(' << cur.second << ", " << cur.first << ") -> ";
        for (int dir = 0; dir < 4; dir++) {
            int ny = cur.first + dy[dir];
            int nx = cur.second + dx[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (vis[ny][nx] || board[ny][nx] != 1) continue;
            vis[ny][nx] = true;
            Q.push(make_pair(ny, nx));
        }
        
    }
    
    return 0;
}

 

Python - 인접 리스트로 주어진 그래프에 대한 BFS

import collections

graph =[[], [1], [1, 3]] # 인접 리스트로 주어진 그래프


def bfs(start_v):
    discovered = [start_v]
    queue = collections.deque([start_v])
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered

 

연결되어 있고 방문하지 않은 정점들을 전부다 큐에 넣고 방문 처리한다.

 

큐가 빌 때 까지 큐의 맨 앞의 정점에 대해 이를 반복한다.

 

출처

C++ 코드

https://blog.encrypted.gg/941?category=773649 

[실전 알고리즘] 0x09강 - BFS

 

Python 코드

https://book.naver.com/bookdb/book_detail.nhn?bid=16406247 

파이썬 알고리즘 인터뷰