숨바꼭질

문제

숨바꼭질

풀이

수빈이의 위치에서 시작하여 동생을 찾을 때 까지 BFS로 탐색하면 됩니다. 방문 처리할 때 bool 변수 대신 시간을 기록하는 방식으로 하면 됩니다.

코드

Python

from collections import deque
 
POS_LIM = 100_001
 
n, k = map(int, input().split())
time = [-1] * POS_LIM
time[n] = 0
 
queue = deque([n])
while queue:
    cur = queue.popleft()
 
    if cur == k:
        print(time[cur])
        break
 
    for next_ in (cur - 1, cur + 1, cur * 2):
        if 0 <= next_ < POS_LIM and time[next_] == -1:
            time[next_] = time[cur] + 1
            queue.append(next_)

C++

#include <bits/stdc++.h>
using namespace std;
 
constexpr int POS_LIM = 100'001;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, k;
    cin >> n >> k;
 
    vector<int> time(POS_LIM, -1);
    time[n] = 0;
 
    queue<int> q;
    q.push(n);
 
    while (not q.empty()) {
        int cur = q.front();
        q.pop();
 
        if (cur == k) {
            cout << time[cur];
            return 0;
        }
        
        for (int next : {cur - 1, cur + 1, cur * 2}) {
            if (0 <= next and next < POS_LIM and time[next] == -1) {
                time[next] = time[cur] + 1;
                q.push(next);
            }
        }
    }
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static final int POS_LIM = 100_001;
 
    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 tk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(tk.nextToken()), k = Integer.parseInt(tk.nextToken());
 
        int time[] = new int[POS_LIM + 1];
        for (int i = 0; i < POS_LIM; i++)
            time[i] = -1;
        time[n] = 0;
 
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
 
        while (!queue.isEmpty()) {
            int cur = queue.poll();
 
            if (cur == k) {
                bw.write(time[cur] + "");
                bw.close();
                return;
            }
 
            for (int next : Arrays.asList(cur - 1, cur + 1, cur * 2)) {
                if (0 <= next && next < POS_LIM && time[next] == -1) {
                    time[next] = time[cur] + 1;
                    queue.add(next);
                }
            }
        }
    }
}