BFS 알고리즘이란?

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

 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 이는 **그래프 탐색** (하나의 정점으로 시작하여 모든 정점을 한번씩 방문)에 속한다. BFS는 두 노드 사이의 **최단 경로** 및 **임의의 경로** 를 찾을때 사용하며 자료 구조 **큐(Queue)** 를 이용해 탐색을 한다.

유사 알고리즘 : Prim, Dijkstra

 

너비 우선 탐색(BFS) 예제 - Python

 해당 예제는 같은 숫자끼리 땅따먹기로 인접한 같은 숫자끼리의 넓이를 구하는 예제이다. 바로 구현해보기 위한 예제이므로 코드가 지저분하다.. 구현 방식은 방문 여부, 큐(Queue)를 활용하였다.

def solution(v):
    result = [0, 0, 0]
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    visited = [[0 for j in range(len(v)+2)] for i in range(len(v)+2)]
    q = []

    for i in range(len(v)):
        for j in range(len(v)):
            if visited[i][j] == 0:
                typeNum = v[i][j]
                q.append([i, j])

                while True:
                    if len(q) == 0:
                        result[typeNum] += 1
                        break

                    else:
                        qindex = q.pop(0)
                        qx = qindex[0]
                        qy = qindex[1]
                        for idx in range(4):
                            nextX = qx + dx[idx]
                            nextY = qy + dy[idx]
                            if nextX < len(v) and nextX >= 0 and nextY >= 0 and nextY < len(v):
                                if v[nextX][nextY] == typeNum and visited[nextX][nextY] == 0:
                                    q.append([nextX, nextY])
                                    visited[nextX][nextY] = 1

    # if visited[len(v)-1][len(v)-1] == 0:
    #    result[v[len(v)-1][len(v)-1]] += 1
    
    print(result)

 

# 같은 숫자 넓이 구하기 (땅따먹기)
solution([[0, 0, 1, 1], [1, 1, 1, 1], [2, 2, 2, 1], [0, 0, 0, 2]])

 

너비 우선 탐색(BFS) 예제 - Java

해당 예제 또한 위와 같은 땅따먹기이며 구현 방식은 방문 여부, 큐(Queue)를 활용하였다.

class Main {
    private static void solution(int sizeOfMatrix, int[][] matrix) {
        ArrayList ans = new ArrayList();

        int[] dx = {0, 1 , 0, -1};
        int[] dy = {1, 0 , -1, 0};

        boolean[][] visited = new boolean[11][11];
        Queue<int[]> q = new LinkedList<int[]>();

        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                if(matrix[i][j] == 1 && visited[i][j] == false) {
                    int count = 0;
                    int[] xy = {i, j};

                    q.add(xy);
                    visited[i][j] = true;
                    
                    while(q.peek() != null) {
                        int[] pollxy = q.poll();
                        int nx = pollxy[0];
                        int ny = pollxy[1];

                        count++;

                        for(int k = 0; k < 4; k++) {
                            int nextX = nx + dx[k];
                            int nextY = ny + dy[k];

                            if(nextX < sizeOfMatrix && nextX >= 0 && nextY >= 0 && nextY < sizeOfMatrix) {
                                if(matrix[nextX][nextY] == 1 && visited[nextX][nextY] == false) {
                                    int[] nextxy = {nextX, nextY};
                                    
                                    q.add(nextxy);
                                    visited[nextX][nextY] = true;
                                }
                            }
                        }
                    }
                    ans.add(count);
                }
            }
        }
        System.out.println(ans.size());
        
        if(ans.size()!=0) {
            Collections.sort(ans);
            
            for(int i = 0; i < ans.size(); i++) {
                System.out.printf("%d ",ans.get(i));
            }
        }
    }

    private static class InputData {
        int sizeOfMatrix;
        int[][] matrix;
    }

    private static InputData processStdin() {
        InputData inputData = new InputData();

        try (Scanner scanner = new Scanner(System.in)) {
            inputData.sizeOfMatrix = Integer.parseInt(scanner.nextLine().replaceAll("\\s+", ""));
            inputData.matrix = new int[inputData.sizeOfMatrix][inputData.sizeOfMatrix];

            for (int i = 0; i < inputData.sizeOfMatrix; i++) {
                String[] buf = scanner.nextLine().trim().replaceAll("\\s+", " ").split(" ");

                for (int j = 0; j < inputData.sizeOfMatrix; j++) {
                    inputData.matrix[i][j] = Integer.parseInt(buf[j]);
                }
            }
        } catch (Exception e) {
            throw e;
        }
        return inputData;
    }

    public static void main(String[] args) throws Exception {
        InputData inputData = processStdin();
        solution(inputData.sizeOfMatrix, inputData.matrix);
    }
}

 

성장에 도움을 주신 개발자분

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

오늘도 감사합니다.