[BFS] 8. 송아지 찾기

 

BFS 방식을 통해 송아지를 찾았다.

 

DFS와는 다르게 재귀함수를 이용하기 보다는 (물론 이용할 수도 있겠지만) Queue를 사용하여 문제를 접근한다.

 

ch[] 라는 배열을 만들어서 이미 들린 자리는 1를 입력하여 향후 다시 그 자리에 오게 되면 더이상 계산하지 않고 제외시키는 방식을 사용했다. 이는 반복해서 일어난 과정을 지움으로써 시간복잡도를 줄이는 효과를 가져온다.

 

-나의 풀이-

runtime error

 

전체적인 문제는 없어 보이지만 런타임 에러가 발생했다.

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

class Main {
    int[] dt = {5, 1, -1};
    int[] ch;
    int L;

    private int BFS(int s, int e) {
        Queue<Integer> Q = new LinkedList<>();
        ch = new int[10001];
        ch[s] = 1;
        Q.offer(s);
        while (!Q.isEmpty()) {
            int len = Q.size();
            for (int i = 0; i < len; i++) {
                int nx = Q.poll();
                for(int x : dt) {
                    if (ch[nx + x] == 0) {
                        if (nx + x == e) return L + 1;
                        Q.offer(nx + x);
                        ch[nx + x] = 1;
                    }
                }
            }
            L++;
        }
        return 0;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        int e = in.nextInt();
        System.out.println(T.BFS(s, e));
    }
}

 

그 이유는 조건의 문제였다. 조건에서 

[[첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다.]]

라고 했기 때문에 조건에 이를 추가해줘야 한다. 그렇지 못하면 ch 인덱스를 넣을 때 음수가 들어올 경우 에러가 발생하면서 런타임 에러가 발생하는 것이다.

 

ch라는 체크용 배열을 만들면 왔던 곳을 한 번 더 오는 경우를 없앨 뿐만 아니라, 음수로 가는 경우도 막아준다. 

하지만 1~10000이라는 조건이 없을 경우 배열로 통해 중복된 값을 확인하는 것은 안 될 것으로 보인다 !!

 

즉, 확인용 배열을 사용하기 위해서는 양수인 정수의 조건이 필요하다.

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

class Main {
    int[] dt = {5, 1, -1};
    int[] ch;
    int L;

    private int BFS(int s, int e) {
        Queue<Integer> Q = new LinkedList<>();
        ch = new int[10001];
        ch[s] = 1;
        Q.offer(s);
        while (!Q.isEmpty()) {
            int len = Q.size();
            for (int i = 0; i < len; i++) {
                int nx = Q.poll();
                for(int x : dt) {
                    int na = nx + x;
                    if (na >=1 && na <= 10000 && ch[na] == 0) {
                        if (na == e) return L + 1;
                        Q.offer(na);
                        ch[na] = 1;
                    }
                }
            }
            L++;
        }
        return 0;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        int e = in.nextInt();
        System.out.println(T.BFS(s, e));
    }
}

 

 

 

-강사님 풀이-

import java.util.*;

class Main{
    int answre = 0;
    int[] dis = {1, -1, 5};
    int[] ch;
    Queue<Integer> Q = new LinkedList<>();
    public int BFS(int s, int e) {
        ch = new int[10001];
        ch[s] = 1;
        Q.offer(s);
        int L = 0;
        while (!Q.isEmpty()) {
            int len = Q.size();
            for (int i = 0; i < len; i++) {
                int x = Q.poll();
                for (int j = 0; j < 3; j++) {
                    int nx = x + dis[j];
                    if (nx == e) return L + 1;
                    if (nx >= 1 && nx <= 10000 && ch[nx] == 0) {
                        ch[nx] = 1;
                        Q.offer(nx);
                    }
                }
            }
            L++;
        }
        return -1;
    }





    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        int e = in.nextInt();
        System.out.println(T.BFS(s, e));
    }
}