본문 바로가기

BOJ/JAVA

숨바꼭질

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
public class Main {
    static int n, k;
    static int visited[] = new int[100001];
    static int dx[] = {-1,1,2};
    static int ans = 987654321;
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken()); //수빈의 위치 
        k = Integer.parseInt(st.nextToken()); //동생의 위치  
        
        for (int i = 0; i < 100001; i++) visited[i] = -1;
        
        bfs(n, k);
        
        System.out.println(ans);
    }
    static void bfs(int start, int dest) {
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(start, 0));
        
        visited[start] = -2;
        
        while(!q.isEmpty()) {
            int now = q.peek().x;
            int cnt = q.peek().cnt;
            q.poll();
            
            if (now == dest) {
                ans = ans > cnt ? cnt : ans;
                break;
            }
            
            for (int i = 0; i < 3; i++) {
                int nx = now;
                
                if (i == 2) nx *= 2;
                else nx += dx[i];
                
                if (nx < 0 || nx > 100000 || visited[nx] != -1continue;
                
                visited[nx] = now;
                q.add(new Pos(nx, cnt+1));
            }
        }
        
    }
    static class Pos {
        int x, cnt;
        
        public Pos(int x, int cnt) {
            this.x = x;
            this.cnt = cnt;
            
        }
    }
}
 
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

'BOJ > JAVA' 카테고리의 다른 글

보물섬  (0) 2020.02.17
영역구하기  (0) 2020.02.17
부분합  (0) 2020.02.17
한 줄로 서기  (0) 2020.02.16
좋은 수열  (0) 2020.02.16