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

문제

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

1697번: 숨바꼭질

 

문제이해

• 수빈이의 위치와 동생의 위치를 입력한다.
• 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 출력한다.

수빈이가 동생을 찾기 위해 사용할 수 있는 방법은 다음과 같다.

1. 수빈이의 기존위치 + 1로 이동하고 1초가 지난다.
2. 수빈이의 기존위치 - 1 로 이동하고 1초가 지난다.
3. 수빈이의 기존위치 * 2 로 이동하고 1초가 지난다

수빈이가 이동했던 자리는 다시 갈 필요가 없고 기억하고 있을 필요도 없기 때문에 너비우선탐색(BFS)을 사용하여 문제를 해결하면 된다.

 

다음은 BFS로 1697번을 해결한 코드이다.

문제풀이

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

int N, K;
bool visit[100001];

void bfs() {
	queue<pair<int, int>> a;
	a.push(make_pair(N, 0));
	while (!a.empty()) {
		int top = a.front().first;
		int chance = a.front().second;
		if (top == K) {
			cout << chance;
			break;
		}
		a.pop();
		if (top * 2 < 100001 && !visit[top * 2]) {
			a.push(make_pair(top * 2, chance + 1));
			visit[top * 2] = true;
		}
		if (top + 1 < 100001 && !visit[top + 1]) {
			a.push(make_pair(top + 1, chance + 1));
			visit[top + 1] = true;
		}
		if (top - 1 > -1 && !visit[top - 1]) {
			a.push(make_pair(top - 1, chance + 1));
			visit[top - 1] = true;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> K;
	if (N >= K)
		cout << N - K;
	else {
		bfs();
	}
}

bool visit [MAX]

visit을 통해 수빈이가 방문했던 좌표는 다시 가지 않도록 해주었다.

void bfs()

queue에 시작 위치를 넣고 bfs를 사용하였다. bfs도중 수빈이의 위치가 동생의 위치와 같게 되는 순간에 걸린 시간을 출력하고 bfs를 종료하였다.

 

문제후기

bfs를 사용해 간단하게 해결할 수 있는 문제였다.