[JAVA] 백준 1697 숨바꼭질

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

1697번: 숨바꼭질

 

- 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0<=N <= 100,000)에 있고, 동생은 점 K(0<=K <=100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 떄 걷는 다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 

 

- 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇초 후인지 구하는 프로그램 

 

 

문제 풀이 

 

- 시간 증가에 가중치가 없고 최단 시간을 찾는 문제이므로 BFS로 풀이 

- 동생을 찾을 때까지 x+1, x-1, 2x를 visited에 넣어 방문했는지 검사 한 후 방문을 하지 않았다면 각각을 큐에 넣어주면 된다. 

 

 

[백준] 1697번 : 숨바꼭질 – JAVA [자바] (tistory.com)

[백준] 1697번 : 숨바꼭질 – JAVA [자바]

 

 

 

 

정답 

 

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

public class Main {
    static int N,K;
    static boolean visited[];
    
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        if(N==K)
        {
            System.out.println(0);
            return;
        }
        
        visited = new boolean[100001];
        
        Queue<Integer> q = new LinkedList<>();
        q.add(N); //수빈이 위치 삽입
        int size = q.size();
        int count = 0;
        
        while(true) {
            count++;
            size = q.size();
            
            for(int i=0; i<size; i++) {
                int x = q.remove();
                visited[x] = true;
                
                if(x-1 == K || x+1 == K || x*2 == K) {
                   System.out.println(count); 
                   return;
                }
                if(x-1 >=0 && !visited[x-1]) {
                    visited[x-1] = true;
                    q.add(x-1);
                }
                if(x+1<=100000 && !visited[x+1]) {
                    visited[x+1] = true;
                    q.add(x+1);
                }
                if(x*2 <=100000 && !visited[x*2]){
                    visited[x*2] = true;
                    q.add(x*2);
                }
            }
        }
    }
}