BFS(너비 우선 탐색) 알고리즘 - JAVA/자바

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

이번 게시글은 자바 24444번 : 너비우선탐색 알고리즘 문제 풀이 및 BFS 설명입니다!

 

BFS(Breadth-First Search)는 그래프 탐색 알고리즘 중 하나로, 시작 정점에서부터 가까운 정점들을 먼저 탐색하는 방식입니다. 즉, 특정 정점에서 출발하여 인접한 정점들을 먼저 탐색하고, 그 다음 레벨의 정점들을 차례대로 탐색합니다.

 

BFS는 주로 큐(Queue) 자료구조를 이용하여 구현하며, 큐는 최단 경로 탐색이나 레벨 탐색에 유용하게 사용됩니다.

 

알고리즘의 동작 원리

1. 초기화:
   • 시작 정점을 큐에 삽입하고, 해당 정점을 방문했다고 표시합니다.
   • 방문 여부를 기록하는 배열(혹은 리스트)을 준비하여 각 정점이 이미 탐색되었는지 추적합니다.
2. 탐색 과정:
   • 큐에서 정점을 하나씩 꺼내어, 그 정점에 인접한 모든 정점을 확인합니다.
   • 인접한 정점 중 아직 방문하지 않은 정점을 큐에 삽입하고, 그 정점이 방문되었음을 기록합니다.
   • 모든 인접 정점을 탐색한 후, 큐에서 다음 정점을 꺼내 탐색을 반복합니다.
3. 종료 조건:
   • 큐가 비게 되면 모든 정점이 탐색되었으므로 알고리즘을 종료합니다.

 

BFS의 의사코드(Pseudo Code)

 

 

백준 너비 우선 탐색 알고리즘 문제 풀이

 

 

 

 

 

입력시,

 

 

첫 번째 줄: 5 5 1 → 정점의 수: 5, 간선의 수: 5, 시작 정점: 1

1 4: 정점 1과 정점 4가 연결

1 2: 정점 1과 정점 2가 연결

2 3: 정점 2와 정점 3이 연결

2 4: 정점 2와 정점 4가 연결

3 4: 정점 3과 정점 4가 연결

 

 

출력시,

> 첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다. 

> i번째 줄에는 정점 i의 방문 순서를 출력한다.

> 시작 정점의 방문 순서는 1이다.

> 시작 정점에서 방문할 수 없는 경우 0을 출력한다.

 

 

 

 

 

1. 그래프 초기화

 

• 정점의 수 N이 5이므로, 크기가 N+1인 인접리스트 graph를 생성한다.
• 무방향 그래프이므로, 각 간선 정보에서 두 정점 u, v를 서로 연결하여 graph에 추가한다.

graph[1] = [4, 2]
graph[2] = [1, 3, 4]
graph[3] = [2, 4]
graph[4] = [1, 2, 3]
graph[5] = []  // 5번 정점은 연결된 다른 정점이 없음

 

위와 같이 graph가 만들어짐

 

• 정점의 인접 정점들을 오름차순 정렬

graph[1] = [2, 4]
graph[2] = [1, 3, 4]
graph[3] = [2, 4]
graph[4] = [1, 2, 3]
graph[5] = []

 

BFS 탐색 과정 (세부 설명)

1. 초기 상태:
   • cnt = 1로 시작하여 visit[start] = cnt++로 visit[1] = 1
   • 큐에는 1이 들어갑니다: queue = [1].
2. 큐에서 1번 정점을 꺼내 탐색:
   • 1번 정점의 인접 정점은 [2, 4]
   • 2번 정점은 아직 방문하지 않았으므로 queue.offer(2)로 큐에 추가하고, visit[2] = cnt++로 visit[2] = 2
   • 4번 정점도 아직 방문하지 않았으므로 queue.offer(4)로 큐에 추가하고, visit[4] = cnt++로 visit[4] = 3
   • 큐 상태: queue = [2, 4].
3. 큐에서 2번 정점을 꺼내 탐색:
   • 2번 정점의 인접 정점은 [1, 3, 4]
   • 1번 정점은 이미 방문했으므로 패스
   • 3번 정점은 아직 방문하지 않았으므로 queue.offer(3)로 큐에 추가하고, visit[3] = cnt++로 visit[3] = 4
   • 4번 정점은 이미 방문했으므로 패스
   • 큐 상태: queue = [4, 3].
4. 큐에서 4번 정점을 꺼내 탐색:
   • 4번 정점의 인접 정점은 [1, 2, 3]
   • 모두 이미 방문했으므로 아무것도 큐에 추가하지 않음
   • 큐 상태: queue = [3].
5. 큐에서 3번 정점을 꺼내 탐색:
   • 3번 정점의 인접 정점은 [2, 4]
   • 모두 이미 방문했으므로 아무것도 큐에 추가하지 않음
   • 큐 상태: queue = [].
6. 큐가 비었으므로 BFS 종료.

 

위 과정을 거치고 나면 최종적으로 방문 배열 순서는

visit[1] = 1
visit[2] = 2
visit[3] = 4
visit[4] = 3
visit[5] = 0  // 5번 정점은 연결된 다른 정점이 없어서 방문되지 않음

 

Full Code

 

import java.io.*;
import java.util.*;

public class Main {
    static int[] visit;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); // 그래프 인접 리스트
    static StringBuilder sb = new StringBuilder();
    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()); // 정점의 수
        int M = Integer.parseInt(st.nextToken()); // 간선의 수
        int R = Integer.parseInt(st.nextToken()); // 시작 정점

        // 그래프 초기화 (정점 번호 1부터 시작하므로 N+1 사용)
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 정보 입력
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph.get(u).add(v); // u에서 v로 가는 간선
            graph.get(v).add(u); // v에서 u로 가는 간선 (무방향 그래프일 경우)
        }

        // 각 정점의 인접 정점들을 오름차순으로 정렬
        for (int i = 1; i <= N; i++) {
            Collections.sort(graph.get(i));
        }

        // BFS를 위한 방문 배열 초기화
        visit = new int[N + 1]; // 정점이 1부터 시작하므로 N+1 크기

        // BFS 실행
        bfs(R);

        for(int i = 1; i<=N; i++)
        System.out.println(visit[i]);
    }

    // BFS 메서드
    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>(); // BFS용 큐
        int count = 1;
        queue.add(start); // 시작 정점을 큐에 삽입
        visit[start] = count++; // 시작 정점 방문 체크

        while (!queue.isEmpty()) {
            int node = queue.poll();
            for(int i=0;i<graph.get(node).size();i++) {
                int nextV = graph.get(node).get(i);

                if(visit[nextV]!=0) continue;

                queue.offer(nextV);
                visit[nextV] = count++;
            }
        }
    }
}