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

알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색

문제 링크: https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

 

 

 

【 풀이 】

 

1차원 배열에서의 BFS 로 해결할 수 있는 문제이다.

수빈이의 현재 점(N) 부터 BFS 를 해서 +1, -1, *2를 했을 때 나오는 위치들을 모두 방문처리 해주고 그 위치에 도달했을 때의 시간을 따로 기록해주면 된다.

 

 

 

 

【 코드 】

 

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

queue<pair<int, int>>pos;
bool visited[100001];
int n, k;

void bfs(int start) {
	pos.push(make_pair(start, 0));
	visited[start] = true;
	while (!pos.empty()) {
		int here = pos.front().first;
		int time = pos.front().second;
		pos.pop();
		if (here == k) {
			cout << time;
			break;
		}
		if (here + 1 >= 0 && here + 1 <= 100000)
			if (!visited[here + 1]) {
				visited[here + 1] = true;
				pos.push(make_pair(here + 1, time + 1));
			}
		if (here - 1 >= 0 && here - 1 <= 100000) 
			if (!visited[here - 1]) {
				visited[here - 1] = true;
				pos.push(make_pair(here - 1, time + 1));
			}
		if (here * 2 >= 0 && here * 2 <= 100000) 
			if (!visited[here * 2]) {
				visited[here * 2] = true;
				pos.push(make_pair(here * 2, time + 1));
			}
	}
}

int main() {
	cin >> n >> k;
	bfs(n);

	return 0;
}