[JAVA] 백준 q1607 - 숨바꼭질

1697번: 숨바꼭질

---

> 의식의 흐름

bfs로 풀면 될 것 같은데..? => 계속 틀렸습니다 뜸

=> 알고 보니 다음 위치를 어디로 할 것인지 순서에 따라 정답/오답이 나왔다,, (자세한 건 풀이에)

 

> 풀이 과정

1. 수빈이의 위치(N), 동생의 위치(K)를 입력 받는다.

2. 만약 수빈이와 동생이 같은 위치라면 0초만에 동생을 찾을 수 있기 때문에 두 명의 위치가 다른 경우에만 bfs를 수행한다.

3. 수빈이의 처음 위치를 덱에 넣기

4. while문 수행

• 덱에서 위치를 poll()하여 다음 위치까지의 시간을 구한다.
• 이때, 다음 위치는 수빈이가 걷는 경우(+1,-1) -> 순간이동 하는 경우(*2) 순으로 수행해야 한다.
  이유) nextLoc*=2를 먼저 수행하고 N=0인 경우, time[nextLoc] = time[0] = 1이 되므로 이후 수행에서 정답+1의 결과가 나오게 된다.

for(int i=0;i<3;i++){
    int nextLoc = nowLoc;
    
    if(i == 0){
        nextLoc += 1;
    } else if(i == 1){
        nextLoc -= 1;
    } else if(i == 2){
        nextLoc *= 2;
    }
    // ...
    time[nextLoc] = time[nowLoc]+1;
    dq.addLast(nextLoc);
}

5. 정답을 출력한다.

 

> 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static final int MAX_NUM = 100_000;
    public static int N, K;
    public static int[] time = new int[MAX_NUM+2];
    public static int ans = 0;

    public static void main(String[] args) throws Exception{
        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){
            bfs(N);
        }

        bw.write(Integer.toString(ans));
        bw.flush();

        br.close();
        bw.close();
    }

    public static void bfs(int loc){
        Deque<Integer> dq = new ArrayDeque<>();
        dq.addLast(loc);

        while(!dq.isEmpty()){
            int nowLoc = dq.pollFirst();

            for(int i=0;i<3;i++){
                int nextLoc = nowLoc;

                if(i == 0){ // 걷기
                    nextLoc += 1;
                } else if(i == 1){ // 걷기
                    nextLoc -= 1;
                } else if(i == 2){ // 순간이동
                    nextLoc *= 2;
                }

                if(nextLoc == K){
                    ans = time[nowLoc]+1;
                    return;
                }

                if(nextLoc<0 || nextLoc>MAX_NUM || time[nextLoc]!=0){
                    continue;
                }

                time[nextLoc] = time[nowLoc]+1;
                dq.addLast(nextLoc);
            }
        }
    }
}