IT/알고리즘

백준 1697 숨바꼭질 자바

어센트 2020. 4. 26. 17:34

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의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지

www.acmicpc.net

BFS로 해결하는 문제였다. 현재위치에서 방문할 수 있는 경우를 3가지로 두고 BFS로 해결하였다.

 

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package DFS_BFS;
import java.io.*;
import java.util.*;
public class 숨바꼭질 {
    public static void main(String[] args) throws Exception {
        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());
        boolean[] vis = new boolean[100000+1];
        int[] hop = new int[100001];
        Queue<Integer> q = new LinkedList<>();
 
        int ans = bfs(0,q,vis,hop,n,k);
        System.out.println(ans);
    }
    static int bfs(int res,Queue<Integer> q,boolean[] vis,int[] hop,int n,int k ){
        int present = n;
        q.add(n);
        vis[n] = true;
        while(!q.isEmpty()  )
        {
            present = q.poll();
            if(present == k){
                return hop[present];
            }
            res++;
 
 
            if(present+1<vis.length && !vis[present+1]){
                hop[present+1] = hop[present]+1;
                vis[present+1] = true;
                q.add(present+1);
            }
            if(present-1>=0 && !vis[present-1]){
                hop[present-1] = hop[present]+1;
                vis[present-1] = true;
                q.add(present-1);
            }
            if(present*2<vis.length && !vis[present*2]){
                hop[present*2] = hop[present]+1;
                vis[present*2] = true;
                q.add(present*2);
            }
 
 
        }
        return res;
    }
}
 
cs