1697(bfs)

첫인상

위치와 (-1,+1,x2) 를 변수로 갖는 dp 문제라고 생각했다.

문제상황

아무리 생각하고 생각해도 저렇게 두가지를 변수로 잡고 dp가 풀리지 않아서 bfs로 접근했다.

풀이

수빈이의 위치에서 동생의 위치까지 최단거리를 bfs를 이용하여 측정했다.

코드

#include<iostream>
#include<queue>
#define pii pair<int,int>
using namespace std;

int x[100005];
bool visit[100005];
int from, to;

int main() {
	queue<pii> q;
	
	cin >> from >> to;

	q.push({ from, 0 });

	while (!q.empty()) {
		int loc = q.front().first;
		int cnt = q.front().second;
		q.pop();

		if (loc == to) {
			cout << cnt;
			break;
		}

		for (int i = 0; i < 3; i++) {
			switch (i) {
			case 0:
				if (loc - 1 >= 0 && !visit[loc - 1]) {
					visit[loc - 1] = true;
					q.push({ loc - 1,cnt + 1 });
					break;
				}
			case 1:
				if (loc + 1 <= 100000 && !visit[loc + 1]) {
					visit[loc + 1] = true;
					q.push({ loc + 1,cnt + 1 });
					break;
				}
			case 2:
				if (2 * loc <= 100000 && !visit[2 * loc]) {
					visit[2 * loc] = true;
					q.push({ 2 * loc,cnt + 1 });
					break;
				}
			}
		}
	}
}