[자바] 백준 1697번 숨바꼭질

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

 

약간 오랜만에 이런 새로운 문제 푸니까 어려웠는데 문제를 풀기 전 어떤 식으로 문제 풀이를 생각했냐하면....

동생이 있는 곳으로 이동할 수 있는 방법이 총 세 가지이기 때문에 bfs에서 탐색할 때 첫 번째 위치에서 갈 수 있는 곳이 총 3개다. 그러니까 상하좌우 문제처럼 다 가봐야한다. 만약 변경한 값이 동생이 있는 곳과 동일하면 바로 return하고 아니라면 queue에 add 하고 변경된 값의 인덱스에 해당하는 visited 값에 1을 더해주면 되는 문제였다.

 

이 문제는 꼭!!!!! 다시 풀어보자. 

import javax.management.Query;
import java.io.*;
import java.util.*;

public class Main {
    static int[] visited = new int[100001];
    static int n, k;
    static Queue<Integer> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        if (n == k) {
            bw.write(String.valueOf(0));
        }
        else{
            bw.write(String.valueOf(bfs(n)));
        }
        bw.flush();
        bw.close();
    }

    static int bfs(int x) {
        visited[x] = 1;
        queue.add(x);
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            for (int i = 0; i < 3; i++) {
                int next;
                if (i == 0) {
                    next = tmp + 1;
                } else if (i == 1) {
                    next = tmp - 1;
                } else {
                    next = tmp * 2;
                }
                if (next == k) {
                    return visited[tmp];
                }

                if (next >= 0 && next < visited.length && visited[next] == 0) {
                    queue.add(next);
                    visited[next] = visited[tmp] + 1;
                }
            }
        }
        return -1;
    }
}