[ 백준 13549 ] 숨바꼭질 3 (C++)

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

13549번: 숨바꼭질 3

 

그냥 bfs로 풀면 된다. 움직일 수 있는 경우의 수는 세 가지이므로 세 가지 조건에 대해 방문처리를 해주고 큐에 push 해주면 된다. 다만 조건문의 순서가 중요하다. 순서가 정답 코드와 동일해야 정답처리된다. 현재 위치를 Now라고 했을 때 조건문의 순서는 아래와 같다.

1. Now * 2

1 → 2 로 이동하는 경우를 생각해보자. 아래 두 가지 방법이 있다.

1 → 2 (1초) +1
1 → 2 (0초) *2

2를 곱하는 게 최소값으로 우선 방문해야 하므로 Now * 2를 먼저 방문 처리 하는 것이 맞다.

2. Now - 1

4 → 6 으로 이동하는 경우를 생각해보자. 아래 두 가지 방법이 있다.

4 → 3 → 6 (1초)
4 → 5 → 6 (2초)

1을 빼고 2를 곱한 게 1을 두 번 더한 결과와 같아지는 경우가 생길 수 있기 때문에 Now - 1 을 먼저 방문 처리 하는 것이 맞다.

3. Now + 1

1, 2번과 겹칠때 가장 후순위이므로 마지막에 위치한다.

 

 

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

int map[100001];

int main() {

	int from, to, loc;
	cin >> from >> to;

	queue<int> q;
	map[from] = 1;
	q.push(from);

	while (!q.empty()) {
		loc = q.front();
		q.pop();

		// 순서가 중요함
		if (loc * 2 <= 100000 && !map[loc * 2]) {
			map[loc * 2] = map[loc];
			q.push(loc * 2);
		}

		if (loc - 1 >= 0 && !map[loc - 1]) {
			map[loc - 1] = map[loc] + 1;
			q.push(loc - 1);
		}

		if (loc + 1 <= 100000 && !map[loc + 1]) {
			map[loc + 1] = map[loc] + 1;
			q.push(loc + 1);
		}

		
	}

	cout << map[to] - 1 << endl;


	return 0;
}