[BAEKJOON] 1697번 : 숨 바 꼭 질

문 제

 

소 스  코 드

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

constexpr int MAX{ 100'000 };

typedef std::queue<std::pair<int, int>> BFS;
bool arr[MAX + 1] = { false , };

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int N, K;

	std::cin >> N >> K;

	BFS bfs;
	bfs.push(std::make_pair(N, 0));
	arr[N] = true;

	int sec{ 0x7fff'ffff };
	while (!bfs.empty()) {
		int pos		{ bfs.front().first };
		int level	{ bfs.front().second };
		bfs.pop();

		if (K == pos) sec = level;

		if (pos > 0 && !arr[pos - 1]) {
			arr[pos - 1] = true;
			bfs.push(std::make_pair(pos - 1, level + 1));
		}
		if (pos < K && !arr[pos + 1]) {
			arr[pos + 1] = true;
			bfs.push(std::make_pair(pos + 1, level + 1));
		}
		if (pos * 2 <= MAX && !arr[pos * 2]) {
			arr[pos*2] = true;
			bfs.push(std::make_pair(pos * 2, level + 1));
		}
	}
	 std::cout << sec << '\n';

	return 0;
}

 

풀 이

 

• BFS ( 너비 기반 탐색 ) 이용

• 이미 갔던 경로를 체크하여, 메모리 낭비를 줄인다.

BFS를 통하여,

위치 x에 대하여

x + 1, x -1, x * 2 가 성립하는데,

만약, x * 2가 K보다 작거나 클 경우 이 두 차이가 가장 적은 값이 정답입니다.

하지만, 이것을 찾기 힘들기 때문에, dp와 같이 경로의 체크를 통하여 반복되는 것을 줄여

Queue를 통하여 구현 하였습니다.

 

 

출 력 값

 

 

문 제  출 처

문제 링크 : www.acmicpc.net/problem/1697

1697번: 숨바꼭질