[백준] 1697번 : 숨바꼭질 - 자바(JAVA)

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

1697번: 숨바꼭질

 

문제 해석

이동할 수 있는 방법은 3가지입니다.

현재 위치에서 -1, 현재 위치에서 +1, 현재 위치에서 *2

 

이동을 하며 X위치에서 K위치로 도달할 수 있는 최단거리를 구해야 합니다.

 

문제 풀이 전 설계

최단거리 이기 때문에 BFS를 사용해서 해결하고자 합니다.

step을 통해서 몇 번 이동했는지를 관리하고 이미 방문한 곳을 또 방문하는 경우는 최단거리가 아니기 때문에 visited 배열을 통해서 중복을 제거합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_1697_숨바꼭질 {

    static class Move{
        int number;
        int step;

        public Move(int number, int step) {
            this.number = number;
            this.step = step;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int result = 0;

        Queue<Move> bfsQ = new LinkedList<>();
        boolean visited[] = new boolean[100001];

        visited[N] = true;
        bfsQ.add(new Move(N,0));

        while(!bfsQ.isEmpty()){
            Move cur = bfsQ.poll();
            int curNum = cur.number;
            int curStep = cur.step;

            if(curNum == K){
                result = curStep;
                break;
            }

            if(curNum-1>=0 && !visited[curNum-1]){
                bfsQ.add(new Move(curNum-1,curStep+1));
                visited[curNum-1] = true;
            }
            if(curNum+1 <= 100000 && !visited[curNum+1]) {
                bfsQ.add(new Move(curNum + 1, curStep + 1));
                visited[curNum + 1] = true;
            }
            if(curNum*2 <= 100000 && !visited[curNum*2]){
                bfsQ.add(new Move(curNum*2, curStep+1));
                visited[curNum*2] = true;
            }
        }

        System.out.println(result);
    }
}