[백준] 13549번 숨바꼭질 3 C++ 문제풀이

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

13549번: 숨바꼭질 3

문제 풀이

처음 문제를 접했을 때 당연히 동생이 수빈이 보다 앞에 있을 거라고 생각해서 코드를 짰다가 틀렸다.

그리고 다음에는 방문 여부를 저장해주지 않아서 메모리 초과가 나왔다.

이 문제는 결국에 2*X 를 갈 때 0초가 걸린다는 것이다 따라서 BFS를 이용해서 문제를 풀 때 2로 나눠지는 경우를 가장 먼저 넣어줘야한다

소스 코드

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

int N, K;
bool visited[100001] = { false };

void bfs() {
	queue<pair<int,int>> que;
	que.push(make_pair(K,0));
	while (!que.empty()) {
		pair<int,int> num = que.front();
		visited[num.first] = true;
		que.pop();
		if (num.first == N) {
			cout << num.second << '\n';
			return;
 		}
		else if (num.first < N) {
			int next_num1 = num.first + 1;
			if (visited[next_num1] == false) {
				que.push(make_pair(next_num1, num.second + 1));
			}
		}
		else {
			int next_num1 = num.first + 1;
			int next_num2 = num.first - 1;

			if (num.first != 0 && num.first % 2 == 0) {
				int next_num = num.first / 2;
				if (visited[next_num] == false) {
					que.push(make_pair(next_num, num.second));
				}
			}

			if (visited[next_num1] == false) {
				que.push(make_pair(next_num1, num.second + 1));
			}

			if (next_num2 >= 0 && visited[next_num2] == false) {
				que.push(make_pair(next_num2, num.second + 1));
			}
		}
	}
}

int main() {

	cin >> N >> K;
	bfs();
}