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

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

1697번: 숨바꼭질

백준 1697번을 풀어봤습니다.

문제 형식이 토마토랑 다르지만 똑같이 BFS로 풀 수 있습니다.

상하좌우 대신 한 칸 앞으로 이동, 한 칸 뒤로 이동, 두 배 앞으로 이동 3개의 좌표를 이용하면 됩니다.

 

아래는 전체 코드입니다.

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

int n, k;

int map[100001];
bool visited[100001];

queue<int> q;

int dx[2] = { -1,1 };

void BFS() {
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		visited[x] = 1;

		for (int i = 0; i < 3; i++) {
			int next_x;
			if (i == 2) {
				next_x = 2 * x;
				if (next_x >= 0 && next_x <= 100000
					&& visited[next_x] == 0) {

					visited[next_x] = 1;
					map[next_x] = map[x] + 1;
					q.push(next_x);
				}
				continue;
			}
			next_x = x + dx[i];
			if (next_x >= 0 && next_x <= 100000
				&& visited[next_x] == 0) {

				visited[next_x] = 1;
				map[next_x] = map[x] + 1;
				q.push(next_x);
			}
		}

	}
}

int main() {
	cin >> n >> k;
	q.push(n);
	BFS();

	cout << map[k];
	return 0;
}