[백준 1697] 숨바꼭질 (C++/Python)

C++)

#include <iostream>
#include <algorithm>
#include <queue>
#define MAX_SIZE 100002

using namespace std;

queue<int> q;
int ans[MAX_SIZE];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, k;
	cin >> n >> k;

	q.push(n);

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		if (cur == k)
			break;

		if (cur - 1 >= 0 && ans[cur - 1] == 0) {
			ans[cur - 1] = ans[cur] + 1;
			q.push(cur - 1);
		}
		if (cur + 1 <= MAX_SIZE && ans[cur + 1] == 0) {
			ans[cur + 1] = ans[cur] + 1;
			q.push(cur + 1);
		}
		if (cur * 2 <= MAX_SIZE && ans[cur * 2] == 0) {
			ans[cur * 2] = ans[cur] + 1;
			q.push(cur * 2);
		}
	}

	cout << ans[k];

	return 0;
}

 

 

 

Python)

import sys
from collections import deque

read = sys.stdin.readline

n, k = map(int, read().rstrip().split())
visited = [0] * 100002
q = deque()
q.append(n)

while q:
    cur = q.popleft()

    if cur == k:
        break

    if cur + 1 <= 100000 and visited[cur + 1] == 0 :
        visited[cur + 1] = visited[cur] + 1
        q.append(cur + 1)

    if cur - 1 >= 0 and visited[cur - 1] == 0 :
        visited[cur - 1] = visited[cur] + 1
        q.append(cur - 1)

    if cur * 2 <= 100000 and visited[cur * 2] == 0:
        visited[cur * 2] = visited[cur] + 1
        q.append(cur * 2)

print(visited[k])