[백준] 1697 숨바꼭질

단계별로 풀어보기 DFS와 BFS의 8단계 문제

1697번: 숨바꼭질

최솟값을 구하는 것이므로 BFS로 풀었다. 30분 정도 걸렸다.

from sys import stdin
n, k = list(map(int, stdin.readline().split()))
import collections
q = collections.deque()
q.append((n, 0))
visited = [False] * (max(n, k) + 2)
while q:
    cur = q.popleft()
    if cur[0] == k:
        print(cur[1])
        break
    if not visited[cur[0]]:
        visited[cur[0]] = True
    else:
        continue
    if cur[0] + 1 < (max(n, k) + 2) and not visited[cur[0] + 1]:
        q.append((cur[0] + 1, cur[1] + 1))
    if cur[0] - 1 >= 0 and  not visited[cur[0] - 1]:
        q.append((cur[0] - 1, cur[1] + 1))
    if 2 * cur[0] < (max(n, k) + 2) and not visited[2 * cur[0]]:
        q.append((2 * cur[0], cur[1] + 1))

 

23일 뒤에 C++로 다시 풀어봤다.

#include <iostream>
#include <tuple>
#include <queue>
#include <vector>
using namespace std;


int main() {
	int n, k;
	cin >> n >> k;
	queue<pair<int, int>> q;
	q.push(make_pair(n, 0));
	vector<bool> visited(100001);
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		if (cur.first == k) {
			cout << cur.second;
			break;
		}
		visited[cur.first] = true;
		if(cur.first - 1 >= 0 && !visited[cur.first - 1])
			q.push(make_pair(cur.first - 1, cur.second + 1));
		if(cur.first + 1 <= 100000 && !visited[cur.first + 1])
			q.push(make_pair(cur.first + 1, cur.second + 1));
		if(cur.first * 2 <= 100000 && !visited[cur.first * 2])
			q.push(make_pair(cur.first * 2, cur.second + 1));
	}
	return 0;
}