[문제풀이] 07-08. 송아지 찾기1

인프런, 자바(Java) 알고리즘 문제풀이

Recursive, Tree, Graph - 0708. 송아지 찾기1(BFS)

🗒️ 문제

🎈 나의 풀이

	 private static int solution(int n, int m) {
        int answer = 0;
        Queue<Integer> Q = new LinkedList<>();
        Q.add(n);

        while(true) {
            int len = Q.size();

            for(int i=0; i<len; i++) {
                int x = Q.poll();
                if(x == m) return answer;

                if(x < m - 5) Q.add(x + 5);
                else if(x < m) {
                    Q.add(x + 5);
                    Q.add(x + 1);
                } else Q.add(x - 1);
            }
            answer++;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        System.out.println(solution(n, m));
    }

🖍️ 강의 풀이

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

💬 짚어가기

해당 문제는 BFS(Breadth-First Search) : 너비 우선 탐색을 이용하여 풀 수 있다.
나의 풀이에서는 Queue를 이용하여 기본적으로 너비 우선 탐색을 할 수 있도록 구성하고,
다음 3가지 조건을 두어 최소한의 연산을 수행하도록 하였다.

1. 현재 크기가 m-5보다 작은 경우 : Q.add(x + 5)
   이 경우에는 5칸을 앞으로 가는 것이 최적의 수이기 때문이다.
2. 현재 크기가 m보다 작고 m-5보다 큰 경우 : Q.add(x + 5), Q.add(x + 1)
   이 때부터는 최적의 수를 찾기 위해 두 경우 모두 탐색을 수행한다.
3. 현재 크기가 m보다 큰 경우 : Q.add(x - 1)
   이 경우에는 1칸 뒤로 가는 것이 최적의 수이다.

위와 같은 조건을 통해 문제를 해결할 수 있다.

강의에서는 현재 좌표의 탐색 여부를 보관할 수 있는 배열을 두어 중복적인 탐색을 없애도록
구성하여 문제를 해결하였다.