백준 13549번 숨바꼭질 3 파이썬, C++

리뷰

BFS를 통한 풀이, 기존 숨바꼭질 보다 조건이 추가되었다, 순간 이동 시 소요되는 시간이 사라졌음

 

문제 풀이

1. n, k값을 입력 받고 bfs의 인자로 n, k , 0을 보내준다.
2. while루프를 돌기 전에 큐에 현재 위치와 시간 정보를 담아주고 100001 크기의 방문 배열을 false로 초기화 한다.
3. 현재 위치를 true로 설정하고 while루프를 시작한다.
4. 이동할 수 있는 위치는 총 세가지다 x - 1, x + 1, x * 2 이 중 순간이동을 하는 경우는 시간이 소요되지 않는다.
5. 시간을 소요하지 않는 순간이동을 가장 먼저 수행 후 조건에 맞다면 큐에 넣어준다.
6. 이후 뺄셈, 덧셈 순으로 조건이 맞을 경우 큐에 추가해 준다.
7. bfs종료 후 리턴값을 출력하면 된다.

 

참고 사항

덧셈과 곱셈을 할때 k와 뺄셈한 거리보다 클 경우 큐에 다음 위치를 추가해 줄 필요가 없다. (어떤 방법으로든 뺄셈보다 늦기 때문)

 

 

정답 코드

파이썬 코드

import collections


def bfs(n, k, time):
    q = collections.deque([(n, time)])
    v = [False] * 100001
    v[n] = True
    while q:
        x, time = q.popleft()
        if x == k:
            return time
        nx1 = x - 1
        nx2 = x + 1
        nx3 = x * 2
        if abs(k - nx1) > abs(k - nx3) and 0 <= nx3 < 100001 and not v[nx3]:
            v[nx3] = True
            q.append((nx3, time))
        if 0 <= nx1 < 100001 and not v[nx1]:
            v[nx1] = True
            q.append((nx1, time + 1))
        if abs(k - nx1) > abs(k - nx2) and 0 <= nx2 < 100001 and not v[nx2]:
            v[nx2] = True
            q.append((nx2, time + 1))


n, k = map(int, input().split())
print(bfs(n, k, 0))

 

C++ 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int bfs(int start, int time, int k) {
	queue<pair<int, int>> q;
	vector<bool> v(100001, false);
	q.push({ start, time });
	v[start] = true;
	while (!q.empty()) {
		int x = q.front().first;
		time = q.front().second;
		q.pop();
		if (x == k) return time;
		int nx1 = x * 2, nx2 = x - 1, nx3 = x + 1;
		if (abs(k - nx1) < abs(k - nx2) && 0 <= nx1 && nx1 < 100001 && !v[nx1]) {
			v[nx1] = true;
			q.push({ nx1, time });
		}
		if (0 <= nx2 && nx2 < 100001 && !v[nx2]) {
			v[nx2] = true;
			q.push({ nx2, time + 1});
		}
		if (abs(k - nx3) < abs(k - nx2) && 0 <= nx3 && nx3 < 100001 && !v[nx3]) {
			v[nx3] = true;
			q.push({ nx3, time + 1 });
		}
	}
}

int main() {
	int n, k;
	cin >> n >> k;
	cout << bfs(n, 0, k);
}