[백준]백준 1697번(C++)

 

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

1697번: 숨바꼭질

이 문제가 왜 BFS 문제일까? BFS문제로 풀지 않고 막무가내로 경로를 쫓아가보자.

수빈이가 5에서부터 동생을 찾으러 간다고 가정해보자.

1) 5에서 갈 수 있는 곳은 4, 6, 10 이며 모두 1초가 걸린다.

2) 4, 6, 10에서 각각 갈 수 있는 곳들은 그림 2층에 나와있다 (3 5 8 5 7 12가 나열된 곳)

3) 2층에서 3층으로 갈 수 있는 곳들을 보면 6 과 10이 나오는데, 이는 이미 1층에서 갈 수 있었던 곳이다.

-> 즉, 수빈이가 1초만에 갈 수 있던 곳이 6과 10번이었다.

-> 그러나 3층까지 조사를 하면 1초만에 갈 수 있던 6번과 10번 지점을 3초에 걸려 가야한다.

4) 최단경로를 구해야 하는데 이 과정은 비효율적이다.

 

이를 해결하기 위해서는 이미 방문했던 곳은 다시 방문하지 않아도 되며, 계층 순서대로 탐색하면 된다.

우리는 이렇게 문제를 해결하는 알고리즘을 BFS라고 부르기로 했었다. 따라서 이 문제는 BFS로 푸는 문제가 맞다. 

 

왜 DFS는 되지 않을까?

DFS는 방문 후 작업을 한 다음에 해당 지점을 방문처리를 하지만,

BFS는 방문처리를 한 뒤 방문 후 작업을 시작한다.

이 과정에서 이미 방문했던 지점들은 걸러지고 방문하지 않았던 곳들에서 작업이 가능한 것이다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>

using namespace std;

bool visited[100001] = { false, };
int N, K;

int bfs(int point, int d);
int main()
{
	scanf("%d %d", &N, &K);
	visited[N] = true;
	printf("%d", bfs(N, 0));
}

int bfs(int point, int d) {
	queue<pair<int, int>> q;
	q.push({ point, d });

	while (!q.empty()) {
		int next = q.front().first;
		int dist = q.front().second;

		if (next == K) {
			return dist;
		}
		q.pop();

		if (next + 1 <= 100000 && visited[next + 1] != true) {
			q.push({ next + 1, dist + 1 });
			visited[next + 1] = true;
		}
		if (next - 1 >= 0 && visited[next - 1] != true) {
			q.push({ next - 1, dist + 1 });
			visited[next - 1] = true;
		}
		if (next * 2 <= 100000 && visited[next * 2] != true) {
			q.push({ next * 2, dist + 1 });
			visited[next * 2] = true;
		}
	}
}