[백준] 1697번 자바 숨박꼭질

문제 출처 

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

1697번: 숨바꼭질

 

접근 방식 및 풀이

- BFS 활용하는 문제

[Algorithm/개념 정리] - [알고리즘] BFS DFS

불러오는 중입니다...

- 100,000개의 배열을 만들어 n+1, n-1, n*2 번째 방문체크

- 방문체크하다가 n=k인 시점에 Count 값 출력

 

 

 

 

 

소스 코드 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
 
    private static int start;
    private static int end;
 
    private static int[] visited;
 
    private static int res=0;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        start = sc.nextInt();
        end = sc.nextInt();
        visited = new int[100001];
        bfs();
        System.out.println(visited[end]);
    }
    private static void bfs(){
        Queue<Integer> queue = new LinkedList<>();
 
        queue.offer(start);
 
        while (!queue.isEmpty()){
            int n = queue.poll();
            if(n==end) break;
            if(n > 0 && visited[n-1] ==0){
                queue.offer(n-1);
                visited[n-1] = visited[n]+1;
            }
            if(n<100000 && visited[n+1]==0){
                queue.offer(n+1);
                visited[n+1] = visited[n] +1;
            }
            if(n*2<=100000 && visited[n*2]==0){
                queue.offer(n*2);
                visited[n*2] = visited[n] +1;
            }
        }
    }
}
 

 

 

결과