[백준] 알고리즘 1697번 - 숨바꼭질문제

문제

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include<memory.h>
#include <stdio.h>
using namespace std;
const int MAX = 200000;
int n, k;
bool check[MAX+1];
int dist[MAX + 1];
queue<int> qu;
void bfs(int x) {
	qu.push(x);
	check[x] = true;
	while (!qu.empty()) {
		int ox = qu.front();
		qu.pop();
		if (ox + 1 <= MAX) {
			int nx = ox + 1;
			if (!check[nx]) {
				check[nx] = true;
				dist[nx] = dist[ox] + 1;
				qu.push(nx);
			}
		}
		if (ox - 1 >= 0) {
			int nx = ox - 1;
			if (!check[nx]) {
				check[nx] = true;
				dist[nx] = dist[ox] + 1;
				qu.push(nx);
			}
		}
		if (ox * 2 <= MAX) {
			int nx = ox * 2;
			if (!check[nx]) {
				check[nx] = true;
				dist[nx] = dist[ox] + 1;
				qu.push(nx);
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> k;
	bfs(n);
	cout << dist[k];
}

해설

BFS를 적용시킬 수 있을때는 가중치가 1일때, 최단거리를 구하라 라는문제에서 사용할 수 있다.

정점과 간선의 수가 작아야하는데, BFS의 시간복잡도는 O(V+E)인데, 적당히 정점이 많아야 시간내에 해결할 수 있다.

또한 가중치가 의미하는 것이 문제의 정답과 같아야 해결할 수 있다.

이동이나, 순간이동을 할 때 드는 비용이 1초라고 한다. 이것은 가중치로 설정할 수 있다. 문제에서도 가장 빠른시간을 원하고 있으니 가중치는 1이다.

수빈이의 위치에서 3가지의 방법을 통해 움직일 수 있다. 즉 수빈이의 위치에서 다른위치로 가려는(위치) 정점들을 연결하기 위한 간선들은 1이라고 볼 수 있다.

또 한가지 생각해봐야 하는게 -1이 있다는 점이다. -1을 이용해서  *2나 +1을 이용해서 최대위치인 10만을 넘어서 -1을 이용해서 최소를 만들 수도 있다는 점이다. 그래서 최대정점인 10만에서 *2를 한 20만을 최대정점으로 설정해준다. 이유는 10만에서 2를 곱하고 또2를 곱하면 절대로 최소시간에 갈 수 없기 때문이다.

이전에는 상하좌우를 가는 BFS를 해보았는데 이 문제는 자기가 갈 수 있는 위치를 조건에 다 부합시키는지 확인해볼필요가 있다.

1) 1을더하기

2) 1을 빼기

3) 2를 곱하기