🎨 송아지 찾기1 (BFS)

🧢 문제

🧢 풀이

🧶 어떤 방법으로 풀까?

위와 같은 방법으로 시작값에서 +1 -1 +5를 한 후 값을 저장 한 후, 각각의 값에다가 다시 한번 +1, -1, +5를 하고 입력값 14가 나올 때 까지 반복을 한다.
값이 14가 나오면 몇 단계를 거쳐서 값이 나왔는지 확인하고 출력하자.

🧢 소스코드

🧶 main메소드

class Main{
	int answer = 0;
    int[] dis = {1 , -1, 5};
    int[] ch;
    Queue<Integer> Q = new LinkedList<>();
    public int BFS(int s, int e){
    }
    
    public static void main(String[] args){
    Main T = new Main();
    Scanner kb = new Scanner(System.in);
    int s = kb.nextInt();
    int e = kb.nextInt();
    System.out.println(T.BFS(s,e));
    }
}

🧶 BFS 메소드

    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 0;
    }

• ch = new int[10001];
  크기가 10001개의 int형 베열을 생성하는 이유는 index[0]을 사용하지 않고, index[1]~index[10000]까지 사용하기 위함이다.

• ch[s] = 1;
  main메소드에서 입력받은 s의 값을 ch배열 index에 넣고 값을 1이라고 저장한다.

• Q.offer(s);
  main메소드에서 입력받은 s의 값을 Q에 넣는다.

• int L = 0
  L은 시작점에서 몇번에 거쳐서 답이 나오는지 확인하는 변수이다.

  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);
                    }
                }
            }

• Q의 크기만큼 반복문을 이용해 값을 하나씩 꺼내어 dis[]배열의 각각의 index와 저장한 후에, 위의 조건문을 만족하면 ch[]배열에 1을 저장한다.

if(nx == e) return L+1

Q에서 꺼내어 dis배열의 각각의 값과 더한 값이 원하는 값인 e와 같다면 현재 레벨에서+1을 해준 값을 return해 준다.

🧶 전체코드

package practice.one;

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

public class Main {

    int answer = 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 0;
    }


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