[Do it] 알코테 자바 9일차

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

그래프 탐색 알고리즘 중 **너비 우선 탐색(BFS, Breadth-First Search)**은 시작 노드에서 출발하여, 시작 노드와 가까운 노드부터 차례대로 방문하는 방식입니다.

깊이 우선 탐색(DFS)과 달리, BFS는 같은 레벨(거리)에 있는 노드들을 먼저 방문하기 때문에 최단 경로 탐색 등에 유용합니다.

---

1. BFS 특징

1. 완전 탐색 방식
   • 그래프의 모든 노드를 한 번씩 방문하여 탐색합니다.
2. FIFO 자료구조 사용
   • BFS는 방문할 노드를 순서대로 처리해야 하기 때문에 큐(Queue) 자료구조를 사용합니다.
   • 큐는 선입선출(FIFO, First In First Out) 구조를 가지고 있어, 먼저 들어온 노드가 먼저 탐색됩니다.
3. 최단 경로 탐색에 적합
   • 가중치가 없는 그래프에서 시작 노드로부터 각 노드까지의 최단 거리를 구할 때 BFS를 활용할 수 있습니다.

---

2. BFS 동작 원리

1. 시작 노드를 큐에 넣고 방문 처리합니다.
2. 큐에서 노드를 하나 꺼내 현재 노드와 연결된 인접 노드들을 방문합니다.
3. 방문하지 않은 인접 노드를 큐에 넣고 방문 처리합니다.
4. 큐가 빌 때까지 2~3번 과정을 반복합니다.

---

3. BFS 순서 예시

1. 시작 노드: A
2. A와 연결된 노드 B, C를 큐에 넣고 방문
3. 큐에서 B를 꺼내 B와 연결된 노드 D, E를 방문 후 큐에 추가
4. 큐에서 C를 꺼내 C와 연결된 노드 F를 방문 후 큐에 추가
5. 큐에서 D, E, F 순서로 꺼내며 탐색 완료

이 과정을 통해 같은 거리의 노드들이 먼저 방문되므로 레벨 순서 탐색이 가능합니다.

---

4. BFS 활용 예시

• 소셜 네트워크에서 친구 추천
• 지도나 길찾기에서 최단 경로 계산
• 퍼즐, 게임에서 최소 이동 횟수 계산
• 그래프의 연결 요소 확인

---

__[029] DFS와 BFS 프로그램

백준 온라인 져지 1260번 https://www.acmicpc.net/problem/1260

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

public class Main {
    static int N, M, V;
    static ArrayList<Integer>[] graph;
    static boolean[] visitedDFS;
    static boolean[] visitedBFS;

    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()); // 정점 개수
        M = Integer.parseInt(st.nextToken()); // 간선 개수
        V = Integer.parseInt(st.nextToken()); // 시작 정점 번호

        // 그래프 초기화
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        // 간선 정보 입력
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a); // 양방향
        }

        // 방문할 때 번호 작은 순서로 처리하기 위해 정렬
        for (int i = 1; i <= N; i++) {
            Collections.sort(graph[i]);
        }

        visitedDFS = new boolean[N + 1];
        dfs(V); // DFS 수행
        System.out.println();

        visitedBFS = new boolean[N + 1];
        bfs(V); // BFS 수행
    }

    // 깊이 우선 탐색
    static void dfs(int v) {
        visitedDFS[v] = true;
        System.out.print(v + " ");
        for (int next : graph[v]) {
            if (!visitedDFS[next]) {
                dfs(next);
            }
        }
    }

    // 너비 우선 탐색
    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visitedBFS[start] = true;

        while (!queue.isEmpty()) {
            int v = queue.poll();
            System.out.print(v + " ");

            // queue에 인접 노드를 넣기 전에 주석 처리 가능
            for (int next : graph[v]) {
                // 아직 방문하지 않은 노드만 추가
                if (!visitedBFS[next]) {
                    queue.add(next); // 큐에 넣음 → 나중에 방문할 예정
                    visitedBFS[next] = true; // 방문 체크 미리 함 → 중복 enqueue 방지
                }
            }
        }
    }
}

__[030] 미로 탐색하기

백준 온라인 져지 2178번 https://www.acmicpc.net/problem/2178

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

public class Main {
    // 상, 하, 좌, 우 이동을 위한 좌표 배열
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken()); // 미로 세로 크기
        int M = Integer.parseInt(st.nextToken()); // 미로 가로 크기
        
        int[][] maze = new int[N][M]; // 미로 배열
        boolean[][] visited = new boolean[N][M]; // 방문 여부 체크
        
        // 미로 입력 받기
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                maze[i][j] = line.charAt(j) - '0'; // '1' -> 1, '0' -> 0
            }
        }
        
        // BFS 탐색 시작
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0}); // 시작점 (0,0)
        visited[0][0] = true;
        
        // 시작점은 이미 지나간 칸 1
        int[][] distance = new int[N][M]; 
        distance[0][0] = 1;
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];
            
            // 상하좌우 이동
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                // 미로 범위 밖이면 패스
                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                
                // 이동할 수 없는 칸이거나 이미 방문한 칸이면 패스
                if (maze[nx][ny] == 0 || visited[nx][ny]) continue;
                
                // 이동 가능하면 큐에 넣고 거리 갱신
                queue.add(new int[]{nx, ny});
                visited[nx][ny] = true;
                distance[nx][ny] = distance[x][y] + 1;
            }
        }
        
        // 도착점(N-1, M-1)까지의 최소 칸 수 출력
        System.out.println(distance[N-1][M-1]);
    }
}

__[031] 트리의 지름 구하기

백준 온라인 져지 1167번 https://www.acmicpc.net/problem/1167

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

public class Main {
    static ArrayList<Node>[] tree;
    static boolean[] visited;
    static int maxDistance; // 가장 긴 거리
    static int farthestNode; // 가장 먼 노드 번호

    static class Node {
        int vertex;
        int weight;

        Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int V = Integer.parseInt(br.readLine());

        // 트리 초기화
        tree = new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) {
            tree[i] = new ArrayList<>();
        }

        // 입력 받기
        for (int i = 0; i < V; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            while (true) {
                int to = Integer.parseInt(st.nextToken());
                if (to == -1) break; // -1이면 입력 종료
                int weight = Integer.parseInt(st.nextToken());
                tree[from].add(new Node(to, weight));
            }
        }

        // 1. 임의의 노드(1번)에서 가장 먼 노드를 찾는다.
        visited = new boolean[V + 1];
        maxDistance = 0;
        farthestNode = 0;
        bfs(1);

        // 2. 그 노드에서 다시 BFS를 수행하여 가장 먼 거리 = 트리의 지름
        visited = new boolean[V + 1]; // 방문 초기화
        maxDistance = 0;
        bfs(farthestNode);

        // 트리의 지름 출력
        System.out.println(maxDistance);
    }

    static void bfs(int start) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(start, 0));
        visited[start] = true;

        while (!q.isEmpty()) {
            Node cur = q.poll();

            // 현재까지의 거리와 최대 거리 비교
            if (cur.weight > maxDistance) {
                maxDistance = cur.weight;
                farthestNode = cur.vertex;
            }

            // 인접 노드 탐색
            for (Node next : tree[cur.vertex]) {
                if (!visited[next.vertex]) {
                    visited[next.vertex] = true;
                    q.add(new Node(next.vertex, cur.weight + next.weight));
                }
            }
        }
    }
}