숨바꼭질

13549번 : 숨바꼭질3

package Gold_5;

import javax.xml.soap.Node;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class HideAndSeek {
    //진행되는 연산은 3종류 +1,-1,*2 이다 이때 연산 순서도 중요함
    static int min = Integer.MAX_VALUE;
    static int n,k;
    static boolean[] visited;
    static int max = 100000; //수빈이가 이동할 수 있는 최대위치
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        k = sc.nextInt();

        visited = new boolean[max+1]; //위치 범위는 0~10000
        bfs();
        System.out.println(min);


    }

    private static void bfs() {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(n,0)); //수빈이의 초기 위치와 시간(0)을 큐에 넣음
        while(!q.isEmpty()) {
            Node node = q.poll(); //현재위치를 node로 꺼내고 그 위치를 방문한 것으로 처리
            visited[node.x] = true;
            if(node.x == k) min = Math.min(min, node.time); //현재 위치가 동생의 위치 k와 같으면 최소시간 갱신

            if(node.x * 2 <= max && visited[node.x * 2] == false) q.offer(new Node(node.x * 2, node.time));
            if(node.x + 1 <= max && visited[node.x + 1] == false) q.offer(new Node(node.x + 1, node.time + 1));
            if(node.x - 1 >= 0 && visited[node.x - 1] == false) q.offer(new Node(node.x - 1, node.time + 1));
        }
    }
    public static class Node{
        int x;
        int time;
        public Node(int x, int time){
            this.x  = x;
            this.time  = time;
        }
    }
}

문제는 주어진 시작 위치 n 에서 동생의 위치 k 까지 이동하는 데 필요한 최소 시간을 계산하는 것이다.

수빈이는 최대 100,000 까지의 위치로 이동할 수 있다.

접근 방식

이 문제를 해결하기 위해 BFS(너비 우선 탐색) 알고리즘을 사용했다. BFS는 최단 경로 문제에 적합한 알고리즘으로 모든 가능한 위치를 탐색하며 최단 경로를 찾아내기 때문임.

코드 작동 방식

1. 초기화 : 사용자의 입력을 받아 수빈이의 초기 위치 n과 동생의 위치를 설정 방문한 위치를 기록하기 위한 배열 visited 를 초기화함

2. BFS 실행: bfs 메서드에서 큐를 사용하여 수빈이의 위치와 경과 시간을 저장합니다. 큐에서 현재 위치를 꺼내고, 동생의 위치와 비교하여 최소 시간을 업데이트합니다.

3. 이동 처리: 현재 위치에서 세 가지 이동 방법(두 배로 이동, +1 이동, -1 이동)을 모두 검사하고, 유효한 이동일 경우 큐에 추가합니다.

4. 최종 결과 출력: 동생의 위치에 도달하는 최소 시간을 출력합니다.