백준 c++ 1697번

문제 설명

 

백준 1697번

 

점에 대한 위치를 1차원 배열로 나타낸다.

 

수빈이의 위치를 N에 넣고 동생의 위치를 K에 넣는다. Q는 수빈이가 갈 수 있는 위치를 저장하는 큐다. 

 

큐에서 값을 뺀 후 수빈이의 위치가 동생의 위치면 함수를 종료시킨다.

 

수빈이가 갈 수 있는 위치는 총 3가지인데 현재 거리로부터 +1, -1, *2 이다. 그래서 for문과 if문을 사용하여 경우의 수를 나누었다. 각각의 경우에 대한 예외처리를 해준 후 배열에 값을 1씩 더해준다.

 

전체 코드

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int dist[100001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, K;
	cin >> N >> K;

	queue<int> Q;

	Q.push(N);
	dist[N] = 0;

	while (!Q.empty()) {
		int cur = Q.front();
		Q.pop();
		if (cur == K) {
			cout << dist[cur];
			return 0;
		}

		for (int i = 0; i < 3; i++) {
			int pos;
			if (i == 0) {
				if (cur == 0)
					continue;
				pos = cur - 1;
				if (dist[pos] > 0)
					continue;
				dist[pos] = dist[cur] + 1;
				Q.push(pos);
			}
			else if (i == 1) {
				if (cur == 100000)
					continue;
				pos = cur + 1;
				if (dist[pos] > 0)
					continue;
				dist[pos] = dist[cur] + 1;
				Q.push(pos);
			}
			else {
				if (cur > 50000)
					continue;
				pos = cur * 2;
				if (dist[pos] > 0)
					continue;
				dist[pos] = dist[cur] + 1;
				Q.push(pos);
			}
		}
	}
	return 0;
}