Java BFS 기초 이해와 문제 풀이

개요 목적

이번 시간에는 BFS 쉬운 문제들을 풀어보면서 BFS 동작 원리와 풀이 방법에 대해서 알아보자.

BFS 넓이 우선 탐색 문제를 통해서 알아보기

이진 트리 노드가 주어졌을 때

목표
0: 1 
1: 2 3 
2: 4 5 6 7
이런식으로 각 레벨 별로 탐색하는 알고리즘을 한번 작성해보자

풀이

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

public class 이진트리순회 {
    static class Node{
        int data;
        Node lt, rt;
        public Node(int val) {
            data=val;
            lt=rt=null;
        }
    }
    public static void BFS(Node node) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        int L = 0;
        while (!queue.isEmpty()) {
            int len = queue.size();
            System.out.print(L+": ");
            for (int i = 0; i < len; i++) {
                Node cur = queue.poll();
                System.out.print(cur.data + " ");
                if (cur.lt != null) {
                    queue.offer(cur.lt);
                }
                if (cur.rt != null) {
                    queue.offer(cur.rt);
                }
            }
            L++;
            System.out.println();
        }
    }
    public static void main(String[] args) {
        Node root = new Node(1);
        root.lt=new Node(2);
        root.rt=new Node(3);
        root.lt.lt=new Node(4);
        root.lt.rt=new Node(5);
        root.rt.lt=new Node(6);
        root.rt.rt=new Node(7);
        BFS(root);
    }
}

이 풀이의 핵심은 int len = queue.size(); 레벨 별로 출력할 데이터 개수를 구하는 것이다.

L=1 일 때 Que에는 {2,3}이 들어 있다. 그리고 이 두개의 값 만 L=1일 때 출력하기 위해 len =2 로 설정해 둔다. 그렇지 않으면 2를 출력한 이후 Que에는 {3,4,5}라는 값이 남게 된다. 그러면, L=1에 3, 4,5 모두 출력 되기 때문에, 처음 레벨 별로 개수를 정해두는 것이 중요하다.

송아지 찾기 BFS 상태 트리

풀이

위 문제와 같이 L을 구한다. 그리고 해당 L에서, 목표하는 숫자가 나오게 되면 BFS를 종료하고 L+1 값 자체가 점프를 뛴 횟수와 같게 된다.

아래와 같이 그림을 그려보면 좀 더 이해가 쉽다.

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

public class 송아지찾기상태트리 {
    static int[] dis = {-1, 1, 5};

    public static int BFS(int S, int E) {
        Queue<Integer> Q = new LinkedList<>();
        Q.add(S);
        while (!Q.isEmpty()) {
						int L = 0;
            int len = Q.size();
            for (int i = 0; i < len; i++) {
                int x = Q.poll();
                for (int di : dis) {
                    int nx = x + di
                    if (nx == E) {
                        return L + 1;
                    }
                    if (nx >= 1 && nx <= 10000) {
                        Q.offer(nx);
                    }
                }
            }
            L++;
        }
        return 0;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        int E = sc.nextInt();
        System.out.println(BFS(S,E));
    }
}