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

1. 조건

- 1초 후 : X+1, X-1로

- 0초 후 : 2*X로

 

2. 입력

- N, K (0 <= N,K <= 100,000)

 

3. 출력

- 최소 시간

 

4. 알고리즘

- 빠른 시간 구하는 것이므로 2*cur부터 방문하기

- 작은거에서 큰걸로 cur-1 > cur+1로 방문하기

 

---

 

C++)

#include <iostream>
#include <algorithm>
#include <queue>
#define MAX_NUM 100001
using namespace std;

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

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

	int visited[MAX_NUM];
	fill(visited, visited + MAX_NUM, -1);

	queue<int> q;
	q.push(n);
	visited[n] = 0;

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

		if (cur == k)
			break;

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

	cout << visited[k];

	return 0;
}

 

 

 

Python)

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().rstrip().split())
max_num = 100001

visited = [-1] * max_num

q = deque()
q.append(n)
visited[n] = 0

while q:
    cur = q.popleft()

    if cur == k:
        break

    if 2*cur < max_num and visited[2*cur] == -1:
        visited[2*cur] = visited[cur]
        q.append(2*cur)

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

print(visited[k])