[JAVA] 알고리즘 문제풀이 기초 - BFS

BFS (넓이 우선 탐색)

기초 구현

import java.util.*;

class Node {
    int data;
    Node lt, rt;
    public Node(int val) {
        data = val;
        lt=rt=null;
    }
}

public class Main {

    Node root;
    public void BFS(Node root){
        Queue<Node> Q = new LinkedList<>();
        Q.add(root);
        int L = 0;
        while(!Q.isEmpty()){
            int len = Q.size();
            System.out.print(L+" : ");
            for(int i=0; i<len; i++){
                Node cur = Q.poll();
                System.out.print(cur.data+" ");
                if(cur.lt!=null) Q.offer(cur.lt);
                if(cur.rt!=null) Q.offer(cur.rt);
            }
            L++;
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Main tree = new Main();
        tree.root=new Node(1);
        tree.root.lt=new Node(2);
        tree.root.rt=new Node(3);
        tree.root.lt.lt=new Node(4);
        tree.root.lt.rt=new Node(5);
        tree.root.rt.lt=new Node(6);
        tree.root.rt.rt=new Node(7);
        tree.BFS(tree.root);
    }
}

정리
1. 문제 풀이하기 전 BFS 기본 구조를 작성 해봄

송아지 찾기 1(BFS : 상태트리탐색)

설명 : 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.
입력 : 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다.
출력 : 점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다.
풀이 1

import java.util.*;

public class Main {

    public void BFS(int st, int ed){
        Queue<Integer> q = new LinkedList<>();
        int lv = 0;
        q.offer(st);
        while (!q.isEmpty()) {
            int size = q.size();
            for(int i=0; i<size; i++){
                int num = q.poll();
                if(num+1==ed||num-1==ed||num+5==ed) {
                    System.out.println(lv);
                    return;
                } else {
                    q.offer(num+1);
                    q.offer(num-1);
                    q.offer(num+5);
                }
            }
            lv++;
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int st = scan.nextInt();
        int ed = scan.nextInt();

        Main main = new Main();
        main.BFS(st, ed);
    }
}

정리
1. 기초구현때 배운 BFS 형식 참고하여 문제 풀이 함
2. Queue에 Node를 사용하지 않고 바로 int 타입을 직대입해서 적용
3. 정답은 정상적으로 출력되지만 큰수를 적용했을때 time limit이 뜨는 증상이 있어 단축할수 있는 방법을 찾아야 함
풀이 2 (시간단축) ``` java import java.util.*;

public class Main {

public void BFS(int st, int ed){
    int[] arr = new int[10001];
    int[] chk = {-1, 1, 5};
    int lv = 1;

    Queue<Integer> q = new LinkedList<>();
    q.offer(st);
    arr[st]=1;

    while (!q.isEmpty()) {
        int size = q.size();
        for(int i=0; i<size; i++){
            int num = q.poll();
            for (int ch : chk) {
                int param = num+ch;
                if(param>0 && param<10000){
                    if(param==ed) {
                        System.out.println(lv);
                        return;
                    } else {
                        if(arr[param]!=1) {
                            q.offer(param);
                            arr[param] = 1;
                        }
                    }
                }
            }
        }
        lv++;
    }
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int st = scan.nextInt();
    int ed = scan.nextInt();

    Main main = new Main();
    main.BFS(st, ed);
} } ```

정리
1. 자식노드를 뻗어나가면서 중복숫자들을 계속 체크하면서 발생한 시간 낭비 문제
2. 조건범위에 맞추어 빈 배열을 만들고 이미 체크한 수는 1로 바뀌게 함
3. 트리에서 자식 노드를 뻗어 만들때 이미 확인했던(=배열값이 1인) 수는 작업을 건너뛰도록 함

IM

BFS (넓이 우선 탐색)

송아지 찾기 1(BFS : 상태트리탐색)