[알고리즘 / 백준] 1697 - 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

문제는 위와 같으며 현재 위치에서 갈 수 있는 위치(+1, -1, *2)를 순차적으로 방문(BFS 탐색)하면 문제를 해결할 수 있습니다.

 

수빈이의 위치가 5이고 동생의 위치가 12라고 할 때 갈 수 있는 위치를 모두 탐색하며 이전에 방문하지 않은 새로운 위치를 방문한 경우 이전까지 걸린 시간 + 1을 하여 해당 위치에 도달한 시간을 구한 뒤 동생의 위치와 현재 위치가 같아지는 경우 해당 위치까지 걸린 시간을 출력하면 됩니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
from collections import deque

MAX = 100001
n, k = map(int, stdin.readline().split())
array = [0] * MAX  # 해당 위치(인덱스)를 방문하는데 걸린 거리


def bfs(v):
    q = deque([v])
    while q:
        now_pos = q.popleft()
        if now_pos == k:
            return array[now_pos]
        for next_pos in (now_pos - 1, now_pos + 1, now_pos * 2):
            if 0 <= next_pos < MAX and not array[next_pos]:  # 다음 위치가 범위 내에 있고 지금까지 방문한 적이 없는 경우
                array[next_pos] = array[now_pos] + 1
                q.append(next_pos)


print(bfs(n))

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    static int MAX = 100001;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] nk = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] array = new int[MAX];

        System.out.println(bfs(nk, array));
    }

    private static int bfs(int[] nk, int[] arr) {
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(nk[0]);

        while (!deque.isEmpty()) {
            int nowPos = deque.pollFirst();
            if (nowPos == nk[1]) {
                return arr[nowPos];
            }

            int[] tmp = {nowPos - 1, nowPos + 1, nowPos * 2};
            for (int nextPos : tmp) {
                if ((nextPos >= 0 && nextPos < MAX) && arr[nextPos] == 0) {
                    arr[nextPos] = arr[nowPos] + 1;
                    deque.add(nextPos);
                }
            }
        }

        return 0;
    }
}