[백준 1697] - [bfs] - 숨바꼭질

문제 링크 : https://www.acmicpc.net/problem/1697

---

이 문제 힌트에 백트래킹으로 돼 있어서 백트래킹으로 풀었다가 후회하고 제일 간단한 단순 bfs로 풀었다.

분명 백트래킹으로 풀 수 있는 문제긴 하다. 

하지만 쉽게 풀 수 있는 방식이 있었기에 이번에는 쉬운 방식으로 풀려고 한다.

간단하게 생각해서 1회전에 방문하는 위치 는 n-1, n+1, n*2가 되고 i번 만큼 반복하면서 목표 위치에

도달했을때의 반복 횟수를 리턴해주면 된다.

소스

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    
    public static int start;
    public static int end;
    
    public static int[] visited;
    
    public 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]);
    }
    public 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;
            }
        }
    }
}