[Java | 알고리즘] BFS - 너비 우선 탐색

BFS (Breadth First Search)

• 가까운 노드부터 우선적으로 탐색 (넓게 탐색)
• 그래프 탐색에 사용
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾을 때 사용
• 큐를 이용해 구현 (선입선출)

특징

• 시작 노드에서 시작해 거리에 따라 단계별로 탐색
• 재귀적으로 동작하지 않음
• 어떤 노드를 방문했는지에 대한 여부를 반드시 검사해야함
  => 검사하지 않을 시 무한 루프

사용 예시

• 그래프의 부분을 찾을 때
• 그래프의 깊이가 다를 때
• 최단 경로 탐색
• 그래프 사이클 찾기
• 그래프 연결요소 찾기

그래프 구현에 따른 시간복잡도

인접리스트

• 노드의 개수가 많고, 간선의 수가 적을 때

인접행렬

• 노드의 개수가 적고, 간선의 수가 많을 때

	인접리스트	인접행렬
특정 간선 검색	O(degree(N) : 해당 노드의 차수	O(1)
정점의 차수 계산	O(degree(N))	O(N)
전체 노드 탐색	O(E)	O(N^2)
메모리	N+E	N^2

수행 과정

1. 시작 노드를 방문 (방문한 노드는 체크 시작)
   • 큐에 방문한 시작 노드를 삽입
   • 초기 상태의 큐에는 시작 노드만 저장
2. 큐에서 꺼낸 노드와 인접한 노드 방문
   • 큐에서 시작 노드 꺼낸 후 인접 노드 큐에 삽입
   • 큐에 삽입된 노드 방문
   • 인접한 노드들 중 방문하지 않은 노드 모두 큐에 삽입
   • 인접한 추가할 노드가 없다면 큐에서 노드 꺼냄
   • 큐가 모두 비면 탐색 종료

구현 시 주의

• 시작 노드 방문한 표시 반드시 남기기
• 큐에서 뺼 때가 아닌 넣을 떄 방문했다는 표시 남기기
• 이웃한 노드가 배열의 범위를 벗어났는지에 대한 체크 잘 하기

구현

인접 리스트 + 큐 사용 방법

import java.util.LinkedList;
import java.util.Queue;

public class BFS {
	// 인접 리스트 방법
    static int[][] graph = {
            {},
            {2,3,7},
            {1,3,5},
            {1,2},
            {6,8},
            {2},
            {4,7,8},
            {1,6},
            {4,6}
    };
    public static void main(String[] args) {
        System.out.printf(bfs(1));
    }
    static String bfs(int start) {
        StringBuilder sb = new StringBuilder();
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.length];

        // 시작 노드 큐에 삽입
        queue.add(start);

        // 시작 노드 방문
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            sb.append(node + " ");

            // 꺼낸 노드의 인접 노드 모두 확인
            for (int i = 0; i < graph[node].length; i++) {
                int tmp = graph[node][i];
                // 인접 노드가 방문한 적 없는 노드면
                if (!visited[tmp]) {
                    // 큐에 삽입
                    queue.add(tmp);
                    // 해당 노드 방문
                    visited[tmp] = true;
                }
            }
        }
        // 1, 2, 3, 7, 5, 6, 4, 8
        return sb.toString();
    }
}

인접행렬 + 큐 사용 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BFS {
    static StringBuilder sb = new StringBuilder();
    static boolean[] visited;
    static int[][] graph;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());  //node
        int M = Integer.parseInt(st.nextToken());  // edge
        int V = Integer.parseInt(st.nextToken());  // start

        graph = new int[N+1][N+1];
        visited = new boolean[graph.length];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            // 인접행렬 방법
            graph[x][y] = 1;
            graph[y][x] = 1;
        }
        
        bfs(V);

        System.out.println(sb);

    }

    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            start = queue.poll();
            sb.append(start + " ");

            for (int i = 1; i <= N; i++) {
                if (graph[start][i] == 1 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

BFS, DFS 사용 경우

BFS

• 최단거리 (가중치가 같은 그래프에서)
• 임의의 경로 찾기 (미로탐색)

DFS

• 모든 노드를 확인할 경우
• 모든 경우를 하나하나 다 탐색할 경우 (조합, 순열 모든 경우의 수를 하나하나 다 찾고자 할 때)
• 경로의 특징을 저장해야할 경우 (서로 다른 가중치를 갖고 있거나 제약이 있을 때)