완전탐색의 한 종류 BFS에 대하여

*본 포스팅은 BFS에 대한 학습을 목적으로 작성되었습니다.

 

탐색의 방법을 고민할 때, 전체 노드를 모두 탐색하는 완전 탐색 방법으로 BFS와 DFS가 있습니다

이 두 가지 방법은 완전 탐색을 한다는 공통점이 있지만, 탐색의 순서에 큰 차이가 있습니다.

따라서 주어진 문제에 따라 어떤 방식이 더 효율적일지 판단할 수 있어야 합니다

 

오늘은 먼저 너비우선탐색 BFS에 대해 자세히 알아보겠습니다.

 

• BFS (Breadth First Search) 

너비우선탐색,루트 노드의 자식노드들을 먼저 차례로 방문한 후에, 방문했던 자식 노드 기준, 다시 해당 노드의 자식 노드를 차례로 방문하는 탐색 알고리즘의 한 방법입니다. 횡방향을 우선적으로 탐색합니다.

 

• 구현 방법 

BFS의 경우 노드 하나를 탐색할 때,  같은 너비에 있는 노드들을 모두 탐색하고 다음 너비를 탐색하기에, 탐색하는 순서가

이전 조상 노드에서 추가한 자식노드의 순서를 따릅니다. 이로 인해 선입선출 FIFO (First In First Out)의 자료구조 Queue를 활용하여 구현할 수 있습니다.

 

• 특징

BFS의 경우, 방문 여부를 꼭 검사하여 반복문에서 빠져나오기 위한 장치를 반드시 마련해야 합니다.

이를 위한 장치로 참,거짓을 판단하는 자료형인 boolean을 사용할 수 있습니다.

 

• 입력 형태에 따른 그래프 생성 자료구조

// 2차원 배열
int[][] graph;

// 인접 리스트 = 리스트 + 배열
ArrayList<Integer>[] graph;

// 인접 리스트 = 리스트 + 리스트
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

// 해시맵 + 리스트
Map<Integer, List<Integer>> graph = new HashMap<>();

//Input Example, 간선의 갯수가 주어지는 경우
5      // 간선 V = 5
1 2
1 3
2 4
2 5
3 6

// 2차원 배열
int[][] graph = new int graph[V+1][V+1];  //노드 번호의 값을 idx와 맞춰주기 위한 배열 크기 +1 증가

// 인접 리스트
graph = new ArrayList[V+1];
for(int i = 0; i <= V; i++){
	graph[i] = new ArrayList<>();
} 

//인접 리스트 = 리스트 + 리스트
for(int i = 0; i <= V; i++){
	graph.add(new ArrayList<>());
}

 

• BFS 코드 구현 

public class BFS {
    static List<Integer>[] nodeList;
    static int[] visited;
  
    // 큐 용도로 사용 할 Array Deque 정의
    static int[][] nodes;
    static ArrayDeque<Integer> queue = new ArrayDeque<>();
    public static void main(String[] args) throws Exception {
        // 입력 데이터
        int N = 5;
        nodes = new int[][]{{0, 1}, {0, 2}, {1, 3}, {1, 4}}; //간선의 개수 V = 4
        // 리스트, 배열 초기화
        nodeList = new ArrayList[N];
        for(int i=0; i<N; i++) nodeList[i] = new ArrayList<>();
        visited = new int[N];

        // 입력받은 간선을 간선 리스트에 저장
        // ex) 1-2 : nodeList[1].add(2); nodeList[2].add(1);
        // 무방향성이므로 양쪽을 저장
        for(int[] e : nodes){
            nodeList[e[0]].add(e[1]);
            nodeList[e[1]].add(e[0]);
        }

        queue.clear(); // 큐 초기화
        bfs(0); // 0부터 출발
        System.out.println(nodeList);
    }
    static void bfs(int start) {
        visited[start] = 1; // 0은 방문 처리
        queue.add(start); // 0을 큐에 저장

        while(!queue.isEmpty()){ // 큐에 아무것도 없을때까지 동작
            int cur = queue.poll(); // 큐에서 제일 먼저 넣은 정점을 꺼냄
            for(int next : nodeList[cur]) {
                if(visited[next] == 0) { // 이어진 점이 방문한 곳이 아니면
                    visited[next] = 1; // 방문 처리하고
                    queue.add(next); // 큐에 방문한 정점을 저장
                }
            }
        }
    }

    }
}

 

BFS의 경우 알고리즘 문제에서 DFS와 함께

완전 탐색의 한 유형으로 다양하게 사용될 수 있습니다.

 

핵심 개념인 선입선출, 방문 개념을 적용하여

알고리즘 문제에 적용해보세요

 

다음 포스팅은 이를 활용한

https://www.acmicpc.net/problem/16940 

16940번: BFS 스페셜 저지

알고리즘 풀이로 돌아오겠습니다

 

감사합니다