[백준 C++] 12851번 : 숨바꼭질 2

1. 문제

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

12851번: 숨바꼭질 2

 

2. 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

3. 소스 코드

#include <iostream>
#include <queue>
#define INF 987654321
using namespace std;

int dist[200005];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 초기화
	for (int i = 0; i < 100005; i++)
		dist[i] = INF;

	// 입력
	int N, K;
	cin >> N >> K;

	// BFS 알고리즘
	int case_cnt = 0;	// 가장 빠른 시간으로 찾는 방법의 수
	dist[N] = 0;		// 각 위치마다 걸리는 시간 기록

	queue<int> q;
	q.push(N);			// 처음 수빈이가 있는 위치를 queue에 저장

	while (!q.empty()) {
		int now = q.front();
		q.pop();
		
        // 동생 위치에 도착했을 경우, 더 이상 진행 X
		if (now == K) {
			case_cnt++;
			continue;
		}

		// 1칸 전진할 때,
		if (now + 1 <= 100000) {	// 맵 범위 안 벗어날 때,

			// 걸린 시간이 더 짧거나 같을 경우
			if (dist[now + 1] >= dist[now] + 1) {
				dist[now + 1] = dist[now] + 1;
				q.push(now + 1);
			}
		}
		
		// 1칸 후진할 때,
		if (now - 1 >= 0) {			// 맵 범위 안 벗어날 때,

			// 걸린 시간이 더 짧거나 같을 경우
			if (dist[now - 1] >= dist[now] + 1) {
				dist[now - 1] = dist[now] + 1;
				q.push(now - 1);
			}
		}

		// 2배 전진할 때,
		if (now * 2 <= 200000) {	// 맵 범위 안 벗어날 때,

			// 걸린 시간이 더 짧거나 같을 경우
			if (dist[now * 2] >= dist[now] + 1) {
				dist[now * 2] = dist[now] + 1;
				q.push(now * 2);
			}
		}
	}

	// 출력
	cout << dist[K] << "\n";
	cout << case_cnt;

	return 0;
}

 

4.  유용한 문법 및 알고리즘

5 - 1) BFS

int dist[200005];

for (int i = 0; i < 100005; i++)
	dist[i] = INF;

dist[N] = 0;
queue<int> q;
q.push(N);

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

	if (now == K) {
		case_cnt++;
		continue;
	}

	if (now + 1 <= 100000) {
		if (dist[now + 1] >= dist[now] + 1) {
			dist[now + 1] = dist[now] + 1;
			q.push(now + 1);
		}
	}
		
	if (now - 1 >= 0) {	
		if (dist[now - 1] >= dist[now] + 1) {
			dist[now - 1] = dist[now] + 1;
			q.push(now - 1);
		}
	}

	if (now * 2 <= 200000) {

		if (dist[now * 2] >= dist[now] + 1) {
			dist[now * 2] = dist[now] + 1;
			q.push(now * 2);
		}
	}
}