백준 12851번 숨바꼭질2

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

12851번: 숨바꼭질 2

 

 

 

 

 

<접근방법>

탐색 문제입니다.

1에서 2까지 도달한다고 합시다.

+1, *2 이렇게 두 가지 방법이 있습니다.

즉, 탐색을 해가며 그 지점에 도달한 횟수도 저장해야 합니다.

 

그런데 문제가 있습니다.

1 -> 2 -> 3 -> 2 는 최단 방법이 아니므로 횟수를 저장할 때 걸러야 합니다.

즉, 이것에 대한 처리도 해야 합니다.

 

참고로..

가중치를 거쳐간 숫자의 갯수라고 합시다.

코드상으로 무조건 가중치가 낮은 순으로 탐색이 됩니다.

그러니까 먼저 도달한 방법이 최단코스 입니다.

 

 

 

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int n, k;
int visit[100001];
int dist[100001];

queue<int> q;

void bfs() {
	int res = 0, flag = 0;

	q.push(n);
	while (!flag) {
		int sz = q.size();
		while (sz--) {
			int x = q.front();
			q.pop();

			if (x == k) {
				flag++;
			}

			for (int nx : {x - 1, x + 1, x * 2}) {
				if (0 <= nx && nx <= 100000) {
					if (!dist[nx] || dist[nx] == dist[x] + 1) {
						q.push(nx);
						dist[nx] = dist[x] + 1;
					}
				}
			}
		}
		res++;
	}
	cout << res-1 << '\n';
	cout << flag << '\n';
}

int main() {
	cin >> n >> k;
	bfs();
	return 0;
}

 

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int n, k;
bool visit[100001];

queue<int> q;

void bfs() {
	int res = 0, flag = 0;

	q.push(n);
	while (!flag) {
		int sz = q.size();
		while (sz--) {
			int x = q.front();
			q.pop();

			visit[x] = true;

			if (x == k) {
				flag++;
			}

			for (int nx : {x - 1, x + 1, x * 2}) {
				if (0 <= nx && nx <= 100000) {
					if (!visit[nx]) {
						q.push(nx);
					}
				}
			}
		}
		res++;
	}
	cout << res - 1 << '\n';
	cout << flag << '\n';
}

int main() {
	cin >> n >> k;
	bfs();
	return 0;
}