[Java] BFS - 너비 우선 탐색 구현 (자바 | Java)

[Java] BFS - 너비 우선 탐색 구현

---

BFS (Breadth First Search)

BFS?

BFS는 너비 우선 탐색이라고도 부르며, 코딩테스트에서 빈번하게 나오는 알고리즘이다.
가까운 노드 부터 우선적으로 탐색하며, 기본적으로 그래프 탐색에 사용된다.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고자 할 때 주로 사용된다.
BFS는 자료구조 큐(Queue)를 사용하여 구현 할 수 있다.

특징

• 직관적이지 않다.
  BFS는 루트 노드에서 시작해 거리에 따라 단계별로 탐색한다.
• 재귀적으로 동작하지 않는다.
• 그래프 탐색의 경우 어떤 노드를 방문했는지 그 여부를 반드시 검사해야 한다.
  검사하지 않을시 무한루프에 빠질 수 있다.

로직

이번 포스팅에 사용될 그래프 예시이다. (간선은 양방향이다.)

탐색을 시작할 노드(루트 노드)를 1로 잡는다면, 다음과 같은 과정을 거친다.

1. 큐에 1번 노드를 넣고 방문 했음을 표시한다.
2. 1번과 인접한 노드를 큐에 넣고 방문 처리. (2, 3, 7)
3. 큐에서 노드 하나를 꺼낸다. (FIFO이므로 1번 노드)
4. 인접한 노드가 없으면 3번 과정으로 돌아간다.
5. 인접한 노드가 있고 방문하지 않았으면 큐에 넣고 방문 처리 후 3번 과정으로 돌아간다.
6. 큐가 빌 때까지 반복한다.

위와 같은 과정을 거치고 난 후 결과는 다음과 같다.
1 -> 2 -> 3 -> 7 -> 5 -> 6 -> 4 -> 8

구현

구현 자체의 난이도는 높은 편이 아니다. 그러나 알고리즘 문제를 풀다 보면 단순 구현 뿐만 아니라 해결 과정에서 생각해야 할 것이 더 많기 때문에 깊게, 잘 이해해야 할 것 같다.

public class My_BFS {
    public static void main(String[] args) {

        // 그래프를 2차원 배열로 표현
        // 인덱스와 노드를 일치 시키기 위해 0은 저장하지 않음
        // 1번 인덱스 = 1번 노드, 배뎔의 값은 연결된 노드
        int[][] graph = {{}, {2,3,7}, {1,3,5}, {1,2}, {6,8}, {2}, {4,7,8}, {1,6}, {4,6}};

        // 방문했는지
        boolean[] visit = new boolean[9];

        System.out.println(bfs(1, graph, visit));
        // 예상 결과값 : 1 -> 2 -> 3 -> 7 -> 5 -> 6 -> 4 -> 8 -> 
    }

    static String bfs(int start, int[][] graph, boolean[] visit) {
        StringBuilder sb = new StringBuilder();

        Queue<Integer> queue = new LinkedList<Integer>();

        queue.offer(start);

        visit[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            sb.append(node + " -> ");
            // 큐에서 꺼낸 노드와 연결된 간선 체크
            for (int i = 0; i < graph[node].length; i++) {
                int temp = graph[node][i];
                // 방문하지 않았으면 방문처리 후에 큐에 삽입
                if (!visit[temp]) {
                    visit   [temp] = true;
                    queue.offer(temp);
                }
            }
        }
        return sb.toString();
    }
}

참고

코딩노잼
바킹독 알고리즘