백준 BOJ 1697번

---

접근 방법

 

이동할 수 있는 경우는 +1, -1, x2 세 가지다. 이걸 그래프로 바꿔서 생각해보면, 최단경로 문제로 볼 수 있다.

BFS를 사용해서 문제를 푼다면 실버 1 문제치고는 쉽게 풀 수 있다. 

BFS에 대한 설명은 이전 글을 참고하자.

 

https://edvedv.tistory.com/4?category=1038364 

백준 BOJ 1012번

 

다만 약간 다른 점이 있다면 카운트를 해야한다는 점인데, 이는 visit 배열을 boolean대신 int형으로 바꿔서 다음 단계로 넘어갈 때마다 count++ 해주면 해결할 수 있다.

---

코드

import java.util.*;

public class Main {
   static int N, K;
   static int[] visit = new int[100001];
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      N = in.nextInt();
      K = in.nextInt();
      if(N == K) System.out.println(0);
      else bfs(N);
   }
   public static void bfs(int n){
      Queue<Integer> q = new LinkedList<>();
      q.offer(n);
      visit[n] = 1;
      
      while(!q.isEmpty()){
         int temp = q.poll();
         for(int i = 0; i < 3; i++){
            int next;
            if(i == 0) next = temp + 1;
            else if(i == 1) next = temp - 1;
            else next = temp * 2;

            if(next == K){
               System.out.println(visit[temp]);
               return;
            }
            if(next >= 0 && next < visit.length && visit[next] == 0){
               q.offer(next);
               visit[next] = visit[temp] + 1;
            }
         }
      }
   }
}