BFS (너비 우선 탐색)

BFS (너비 우선 탐색)

• 너비우선탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
• 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행 하므로, 선입선출 형태의 자료구조인 큐를 활용함.

인접 행렬 BFS

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

public class Main {
    static class Node{
        int y;
        int x;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
    static int[][] map;
    static int[][] visited;
    static int N;
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, 1, 0, -1};
    static Queue<Node> queue = new ArrayDeque<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        visited = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        bfs(0, 0);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(visited[i][j] + " ");
            }
            System.out.println();
        }
        br.close();
    }
    static void bfs(int starty, int startx){
        visited[starty][startx] = 1;
        queue.offer(new Node(starty, startx));
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            int y = now.y;
            int x = now.x;
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if(ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
                if(visited[ny][nx] == 0 && map[ny][nx] == 1){
                    visited[ny][nx] = visited[y][x] + 1;
                    queue.offer(new Node(ny, nx));
                }
            }
        }
    }
}
/*
입력
3
1 1 0
0 1 1
1 0 1
출력
1 2 0 
0 3 4 
0 0 5 
 */

인접 리스트 BFS

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

public class Main {
    static List<Integer>[] adj;
    static int[] visited;
    static int V, N;
    static Queue<Integer> queue = new ArrayDeque<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        adj = new List[V + 1];
        for (int i = 0; i < V + 1; i++) {
            adj[i] = new ArrayList<>();
        }
        visited = new int[V + 1];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            adj[from].add(to);
        }

        bfs(1);

        for (int i = 1; i < V + 1; i++) {
            System.out.println(visited[i]);
        }
        br.close();
    }
    static void bfs(int start){
        visited[start] = 1;
        queue.offer(start);
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (Integer integer : adj[now]) {
                if(visited[integer] != 0) continue;
                visited[integer] = visited[now] + 1;
                queue.offer(integer);
            }
        }
    }
}
/*
입력
4 5
1 2
1 3
2 4
3 1
4 3
출력
1
2
2
3
 */

BFS 활용

• 가중치가 1인 그래프나 인접 행렬의 최단 거리를 구할 때, 사용한다.