BOJ1697 숨바꼭질

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

BFS는 visited를 확인을 q에 삽일할 때 해주면 된다.

 

 

import java.io.*;
import java.util.*;
public class Main
{   
    static int n;
	static int m;
	
	
	
	
	public static int bfs(int start){
	    Queue<Integer> q = new LinkedList();
	    int[] visited = new int[100_001];
        q.offer(start);
        while(q.size()>0){
            int cur = q.poll();
            if(cur==m){
                return visited[cur];
            }
            
            if(cur+1<=100_000 && visited[cur+1]==0){
                q.offer(cur+1);                
                visited[cur+1] = visited[cur]+1;
            } 
            if(cur-1>=0 && visited[cur-1]==0){
                q.offer(cur-1);                
                visited[cur-1] = visited[cur]+1;
            } 
            if(2*cur<=100_000 && visited[cur*2]==0){
                q.offer(cur*2);
                visited[cur*2] = visited[cur]+1;
                
            } 
        }
	    return visited[m];
	}
		
    
    
    
    
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input1 = br.readLine().split(" ");
		n = Integer.parseInt(input1[0]);
		m = Integer.parseInt(input1[1]);
		
		int ans = bfs(n);
		System.out.println(ans);
		
		
		
	}
}

import java.util.*;


class Main {
    static int n, k;
    static int[] visited = new int[100001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        Queue<Integer> q = new LinkedList<>();
        q.add(n);
        visited[n] = 1;
        while (!q.isEmpty()) {
            int now = q.poll();
            if (now == k) break;
            int[] next = {now - 1, now + 1, now * 2};
            for (int i = 0; i < 3; i++) {
                if(!isRange(next[i])) continue;
                if (visited[next[i]] == 0) {
                    visited[next[i]] = visited[now] + 1;
                    q.add(next[i]);
                }
            }
        }
        System.out.println(visited[k] - 1);
    }
    static boolean isRange(int x) {
        return x >= 0 && x <= 100000;
    }
}