1.문제

2.코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * Author : YoungSeo Jeon
 * Date : 2021-09-24
 * Description : 백준
 */


public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] visited = new int[100001];
        
        Arrays.fill(visited, Integer.MAX_VALUE);
        
        Queue<Integer> queue = new LinkedList<Integer>();

        queue.add(N);
        visited[N] = 0;
        int time = 0;
        int count = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-->0){
                int curr = queue.poll();

                if(curr == M){
                    count++;
                }

                int temp1 = curr-1;
                int temp2 = curr+1;
                int temp3 = curr*2;

                if(temp1>=0){
                	if(visited[temp1]>=visited[curr]) {
                		queue.add(temp1);
                    	visited[temp1] = visited[curr]+1;
                	}
                }
                if(temp2<=100000){
                	if(visited[temp2]>=visited[curr]) {
                		queue.add(temp2);
                    	visited[temp2] = visited[curr]+1;
                	}
                }
                if(temp3<=100000){
                	if(visited[temp3]>=visited[curr]) {
	                    queue.add(temp3);
	                    visited[temp3] = visited[curr]+1;
                	}
                }
            }
            if(count!=0) {
            	break;
            }
            time++;
        }
        System.out.println(time+"\n"+count);
        br.close();
    }
}

3.Reveiw

이 문제는 숨바꼭질을 변형한 문제이지만 접근방식이 약간 다르다 .

똑같이 BFS로 풀었다. 하지만 queue에 추가해주는 조건이 조금 까다롭다.

나는 동일한 횟수로 접근하는 방법을 구하기 위해서 방문을 했어도

동일한 시간에 접근을 했다면 queue에 추가해주는 방식을 사용하였다.