BFS(넓이 우선 탐색)

BFS(Breadth-First Search)란?

1. 그래프 완전 탐색 기법 중 하나

2. Queue 자료구조로 구현 -> 선입선출(FIFO)

3. 탐색 시작 노드와 가까운 노드를 우선 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때, 최단 경로 보장

 

 

BFS 동작 원리

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

 

1) 시작점을 1로 설정

2) 인접 리스트로 그래프 표현

3) 방문 배열을 boolean으로 표현

 

 

2. 큐에서 노드를 꺼낸 후 노드의 인접 노드를 다시 큐에 삽입

 

1) 큐에서 1을 꺼냄

2) 1의 인접리스트인 2, 3을 큐에 삽입 및 방문 배열 체크(T로 바꿔줌)

 

 

3. 큐 자료구조에 값이 없을 때까지 반복

---

백준 온라인 저지 1260번

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

public class P1260_DFS와BFS {

    static boolean visited[]; // 방문배열
    static ArrayList<Integer> arr[]; // 인접리스트

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 노드 수
        int m = sc.nextInt(); // 에지 수
        int start = sc.nextInt(); // 시작점

        arr = new ArrayList[n+1];
        visited = new boolean[n+1];

        for(int i=1; i<=n; i++) {
            arr[i] = new ArrayList<Integer>();
        }

        for(int i=0; i<m; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();

            arr[s].add(e);
            arr[e].add(s);
        }

        // 번호가 작은 것을 먼저 방문하기 위해 정렬
        for(int i=1; i<=n; i++) {
            Collections.sort(arr[i]);
        }

        DFS(start);
        System.out.println("");

        visited = new boolean[n+1]; // 방문 배열 초기화
        BFS(start);
    }

    static void DFS(int node) {
        visited[node] = true;
        System.out.print(node + " ");

        for(int i=0; i<arr[node].size(); i++) {
            if(!visited[arr[node].get(i)]) {
                DFS(arr[node].get(i));
            }
        }
    }

    static void BFS(int node) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(node);
        visited[node] = true;

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

            for(int i=0; i<arr[newNode].size(); i++) {
                if(!visited[arr[newNode].get(i)]) {
                    visited[arr[newNode].get(i)] = true;
                    q.add(arr[newNode].get(i));
                }
            }
        }

    }
}

 

---

백준 온라인저지 2178번

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 P2178_미로탐색 {

    // 위, 오른쪽, 아래, 왼쪽
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static boolean[][] visited;
    static int[][] A;
    static int N, M;

    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());
        A = new int[N][M];
        visited = new boolean[N][M];

        // 2차원 배열 입력받기
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for(int j=0; j<M; j++) {
                A[i][j] = Integer.parseInt(line.substring(j, j+1));
            }
        }

        BFS(0, 0);
        System.out.println(A[N-1][M-1]);
    }

    private static void BFS(int i, int j) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {i, j});

        while(!q.isEmpty()) {
            int now[] = q.poll();
            visited[i][j] = true;

            // 4방향 탐색
            for(int k=0; k<4; k++) {
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];

                if(x>=0 && y>=0 && x<N && y<M) { // 배열의 범위를 넘어가지 않고
                    if(A[x][y] != 0 && !visited[x][y]) { // 0이 아니고 방문하지 않을 경우
                        // 탐색 가능!
                        visited[x][y] = true;
                        A[x][y] = A[now[0]][now[1]] + 1; // 현재의 depth를 표현!!
                        q.add(new int[] {x, y});
                    }
                }
            }
        }
    }
}