[BOJ]1697-숨바꼭질 (S1)

문제

1697-숨바꼭질

---

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

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

입력

---

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

출력

---

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

문제 풀이

---

이동가능한 위치 3가지

1. 현재위치 - 1
2. 현재위치 + 1
3. 현재위치 * 2

for (int i = 0; i < 3; i++) {
		if (i == 0) {
				next = cur - 1;
    } else if (i == 1) {
        next = cur + 1;
    } else {
        next = cur * 2;
    }
}

dist로 이동한 시간 count

배열이 0으로 초기화 되어있기 때문에 시작점의 값을 1로 지정해주고 이동할 때마다 1씩 증가

값이 0이 아니라면 이미 방문한 지점이기 때문에 다시 방문할 수 없음

최종 결과값을 -1해서 출력

static int MAX_DISTANCE = 200002;
static int[] dist = new int[MAX_DISTANCE];

dist[cur] = 1;
dist[next] = dist[cur] + 1;

전체코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main {
    static int N, K;
    static int MAX_DISTANCE = 200002;
    static int[] dist = new int[MAX_DISTANCE];

    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());

        if (N == K) {
            System.out.println(0);
        } else {
            bfs(N);
        }
    }

    public static void bfs(int cur) {
        Queue<Integer> queue = new LinkedList<>();
        dist[cur] = 1;
        queue.add(cur);

        while (!queue.isEmpty()) {
            cur = queue.poll();
            int next;
            
            if (cur == K) {
                System.out.println(dist[cur]-1);
                return;
            }

            for (int i = 0; i < 3; i++) {
                if (i == 0) {
                    next = cur - 1;
                } else if (i == 1) {
                    next = cur + 1;
                } else {
                    next = cur * 2;
                }
                
	              // 범위내에 존재하는지 확인
	              // dist[next] != 0 이라면 이미 방문한 지점
                if (next >= 0 && next < MAX_DISTANCE && dist[next] == 0) {
                    queue.add(next);
                    dist[next] = dist[cur] + 1;
                }
            }
        }
    }
}