공부 198일차: 백준 1697번 숨바꼭질 자바 java

1697 숨바꼭질

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

1697번: 숨바꼭질

 

 

 

---

백준 1697번 문제 숨바꼭질

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	185568	53330	33602	25.249%

문제

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

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

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

제한

 

예제 입력 1

5 17

예제 출력 1

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

 

 

 

---

과정 생각해보기 & 오답

---

 

역시나 기본적인  BFS 문제

while문 안에서 수빈이가 이동할 수 있는 경우의 수를 모두 고려해야 한다

그림처럼 수빈이 위치에서부터 경우의 수에 따라 -1, +1, *2를 모두 해가며 1씩 더한다

 

중복되는 부분이 많아서 깔끔하게 쓸 수 있는 방법이 없을까 하다가 찾은 게 이 블로그다

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, k;
    static int[] visited = new int[100_001];
    
    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());
    
        bfs();
    }
 
    static void bfs() {
        if(n == k) {
            System.out.println(0);
            return;
        }
 
        Queue<Integer> q = new LinkedList<>();
        q.add(n);    // 수빈이 위치부터 시작
        visited[n] = 1;
        
        
        while(!q.isEmpty()) {
            int now = q.poll();
 
            for(int i = 0; i < 3; i++) {    // 경우의 수 3개
                int next = 0;
                
                if(i == 0) {
                    next = now-1;
                }else if(i == 1) {
                    next = now+1;
                }else {
                    next = now*2;
                }
                
                if(next == k) {
                    System.out.println(visited[now]);
                    return;
                }
                
                if(next > -1 && next < 100_001 && visited[next] == 0) {    // 범위 안 && 아직 방문 전
                    q.add(next);
                    visited[next] = visited[now]+1;
                }
            }
            
        }
    }
}
 

 

 

 

---

재미있는 문제..

효율적인 코드를 어떻게 짤지 혼자서 더 고민해보아야겠다