백준 12851 숨바꼭질 (c++) : 피너클

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

12851번: 숨바꼭질 2

 

흔한 bfs문제다. bfs는 너비 우선 탐색으로 시작 정점에서 가까운 정점들을 우선으로 탐색하는 그래프 알고리즘이다.

 

이 문제에서 주의해야 하는부분은 bfs에서 방문한 정점을 저장하는 부분이다.

5에서 8로 갈때

5 -> 6 -> 7 -> 8

5 -> 10 -> 9 -> 8

이렇게 2가지 상황이 나올수 있다. 첫번째 상황에서 방문을 체크해버리면 두번째 상황이 적용되지 못하니 방문을 저장하는 부분의 위치를 평소와는 다르게 해준다.

queue<pair<int, int>> q;
q.push({ n, 0 });

int ans = 0;
int last = -1;

queue<pair<int, int>> q로 선언해 앞에는 현재 위치가, 뒤에는 현재 위치까지 가는데 걸린 시간을 집어넣는다.

처음 q에는 현재위치 n와 시간이 0이 들어간다.

int ans에는 동생을 찾는 방법의 수가, int last에는 동생을 찾는 가장 빠른 시간이 들어간다.

last를 -1로 선언하는 이유는 도착했는지 도착 못했는지를 구별하기 위함이다.

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

		visited[now] = true;

queue가 빈다면 반복문을 종료한다.

int now에는 현재 위치가, int time에는 현재 위치까지 걸린 시간이 들어간다.

그후 q의 맨 위를 삭제시킨다.

이 다음 방문을 저장한다. q에 집어넣으며 저장하는 것이 아닌 q에서 꺼내며 저장하는 것은 위의 이유와 같다.

if (now == k) {
	if (last == -1) {
		ans++;
		last = time;
	}
	else {
		if (last == time) ans++;
	}
}

만약 현재 위치가 동생의 위치(k)와 같다면

만약 last가 (last는 동생의 위치까지 걸리는 최소의 시간) -1이라면 (-1은 동생의 위치까지 가지 못했다는 뜻이다.)

ans에 1을 추가하고 last를 time으로 갱신시킨다.

만약 last가 -1이 아니라면 (동생의 위치까지 가서 last가 갱신됬다면)

last가 time, 즉 동생의 위치까지 가는 가장 빠른 시간이 현재 위치까지 걸린 시간과 같다면 ans에 1을 추가한다.

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

여기는 문제에 나와있는데로 구현하면 된다.

이동하는 구간이 범위에서 벗어나는지를 확인한뒤 방문한 곳인지를 확인하고 q에 집어넣으면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

int n, k;
bool visited[100001] = { false, };

void bfs() {
	queue<pair<int, int>> q;
	q.push({ n, 0 });

	int ans = 0;
	int last = -1;

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

		visited[now] = true;

		if (now == k) {
			if (last == -1) {
				ans++;
				last = time;
			}
			else {
				if (last == time) ans++;
			}
		}

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

	cout << last << endl << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> k;
	bfs();
}

전체코드다.