백준 1697. 숨바꼭질

알고리즘 기초 문제 중 610 - BFS

숨바꼭질

숨바꼭질 시리즈 중 첫번째 문제

1. 간단 설명

수빈이가 동생과 1차원 직선에서 술래잡기를 한다

수빈이는 왼쪽, 오른쪽으로 이동하거나

무려 순간이동을 할 수 있다

이 때 동생을 잡는 최단시간을 구하는 문제

2. 예시

• 수빈이는 5, 동생은 17에 있는 경우

5 -> 10 (*2) -> 9 (-1) -> 18 (*2) -> 17 로 이동하는 경우 4초만에 찾을 수 있음

3. 알고리즘

수빈이의 현재 위치 N에서 움직일 수 있는 경우의 수는 3가지다

1. 왼쪽으로 이동 (N - 1)

2. 오른쪽으로 이동 (N + 1)

3. 순간이동 (N * 2)

만약 DFS로 깊이 우선 탐색 방법으로 접근한다면?

void DFS(int n, int k, int level) {

	if (n == k) {
		cout << level << '\n';
		return;
	}

	DFS(n - 1, k, level + 1);
	DFS(n + 1, k, level + 1);
	DFS(2 * n, k, level + 1);
}

이런식으로 구현될텐데 DFS 특성상 시간 초과가 발생한다

이런식으로 N-1인 경우를 계속 따라 들어가기 때문

여기선 BFS를 쓰는게 효율적이다

같은 레벨별로 확인하다가 동생과 같은 좌표를 찾으면 된다

필요 변수

• 수빈이와 동생의 좌표 int N, K(0 ≤ N, K ≤ 100,000)
• 방문했던 좌표를 표시할 int or bool visited[100000]

주의 사항

• 한번 방문했던 좌표를 체크해두지 않으면 0 -> 1 -> 0 -> 1 과 같이 반복해서 방문한다. 메모리 초과의 주범임
• 직선의 범위를 벗어나는 경우를 체크. out of index 에러 주의!

4. 소스코드

#include <iostream>
#include <queue>

using namespace std;

#define MAX 100000

int visited[MAX +1];

struct node {
	int pos;
	int second;
};

int main() {
	int N, K;
	cin >> N >> K;

	queue< node > qu;
	qu.push({ N, 0 });
	visited[N] = 1;

	while (!qu.empty()) {
		node now = qu.front();
		qu.pop();

		if (now.pos == K) {
			cout << now.second << '\n';
			return 0;
		}

		if ((0<= now.pos -1 && now.pos -1 <= MAX) && visited[now.pos - 1] == 0 ) {
			visited[now.pos - 1] = 1;
			qu.push({ now.pos - 1, now.second + 1 });
		}
		
		if ((0 <= now.pos +1 && now.pos +1 <= MAX) && visited[now.pos +1 ] == 0) {
			visited[now.pos + 1] = 1;
			qu.push({ now.pos + 1, now.second + 1 });
		}
		
		if ((0 <= now.pos * 2 && now.pos * 2 <= MAX) && visited[now.pos * 2] == 0) {
			visited[now.pos * 2] = 1;
			qu.push({ now.pos * 2, now.second + 1 });
		}
	
	}

	return 0;
}

• 다익스트라를 이용한 풀이 ```cpp #include #include

#define MAX 100000

using namespace std;

int N, K;

int arr[100001] = { 0 };

int main() { cin » N » K; for (int i = 0; i <= MAX; i++) { arr[i] = 21e8; // 거리를 무한으로 세팅 }

arr[N] = 0; // 시작지점 거리

queue<int> qu;
qu.push(N);

while (!qu.empty()) {
	int now = qu.front();
	qu.pop();

	int direct[3] = { -1, 1, now }; // N+N = 2N

	for (int t = 0; t < 3; t++) {
		int next = now + direct[t];

		if (next < 0 || next > MAX) continue; // 맵 밖을 벗어남
		
		// 저장되어 있는 값보다 작다면, 그 값이 최단거리다
		if (arr[now] + 1 < arr[next]) {
			arr[next] = arr[now] + 1;
			qu.push(next);
		}
	}
}

cout << arr[K];

return 0; } ```