[백준]1697 숨바꼭질

요즘 브론즈만 풀었더니 딱히 풀이랄게 없었는데 오랜만에 BFS 실버 !

package baekjoon;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main_1697 {
    static int N, K;
    static int[] visit = new int[100001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        if(N==K) {
            System.out.println(0);
        }
        else {
            bfs(N);
            System.out.println(visit[K]-1);
        }
    }

    public static void bfs(int X) {
        Queue<Integer> q = new LinkedList<>();
        q.add(X);
        visit[X] = 1;
        while (!q.isEmpty()) {
            int x = q.poll();

            // 수빈이가 움직일 수 있는 거리
            if (x-1 >= 0 && visit[x - 1] == 0) {
                visit[x-1] = visit[x]+1;
                q.add(x-1);
            }
            if (x+1 <= 100000 && visit[x + 1] == 0) {
                visit[x+1] = visit[x]+1;
                q.add(x+1);
            }
            if (2*x <= 100000 && visit[2 * x] == 0) {
                visit[2*x] = visit[x]+1;
                q.add(2*x);
            }
        }
    }
}

dfs bfs는 자신있다고 생각했으나 유형이 좀만 달라지면 헤맨다 ㅠ 많이 풀어보는게 답 !

수빈이가 움직일 수 있는 모든 경로에 경과한 시간을 배열에 저장해주고 그 경로를 q에 넣어 동생이 있는 곳에 도달할 때까지 돌렸다.

여러방식으로 풀어본 결과..