[백준 1697/C++] 숨바꼭질

이진중·2022년 6월 3일

문제풀이

DP적 접근

dp가 잠깐 생각 나긴했지만, dp[i]를 적고 풀어보려했다.
dp[i]와 dp[i-1]과 dp[i+1] dp[i/2]의 연관성을 찾아 관계식을 도출해 내서 반복문을 통해 dp[i]를 채워나가면 문제가 풀릴거 같았다. 하지만 앞으로 뒤로 갈수있는 양방향 문제에서 어떻게 짜야할지 얘매했고, 반복을 계속하면서 최신화 완료됫을때 루프를 나오는 방식으로 문제를 해결할수 있지만, 이런문제를 DP로 접근하는건 별로 좋지 않았다.

BFS적 접근

n-1, n+1, n2를 큐에 넣고빼고를 반복하면서 k에 접근해 가는 방식이다.
이렇게되면 O(3^a)으로 시간초과가 날까 걱정햇지만 그렇지 않았다. n이 100,000보다 작거나 같고, 2가 섞여있어서 그런거같다.

메모리 초과

중복체크를 해주지 않으면 메모리 초과가 난다.
큐에 넣을때 중복이 있는지 체크하려고 큐전체를 체크하는건 비효율적이고,
exCheck[i]처럼 이미 체크가 됬던곳인지 아닌지를 체크해주면 된다.

n-1 n-2 n*2의 범위

exCheck의 범위를 넘을 수 없다. 여기서는 exCheck의 범위가 MAX 인덱스까지이므로
MAX-1까지 넣어줘야하므로, x2,x3< MAX 이고, x1>=0이다.

횟수를 기록하기

몇번만에 k에 도착했는지를 기록해야한다.
처음에는 while(q.empty())반복문 안에 cnt 를 하나씩 올렷는데 그렇게 접근하면
큐를 세번씩 넣고 돌리기 때문에 cnt가 과도하게 많이 증가한다.
처음부터 큐에 넣을때 pair<int,int>자료형으로 위치와 횟수자체를 기록해야 한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
#define endl "\n"

#define MAX 100001
int n, k;
queue<pair<int,int>> q;
bool exCheck[MAX];

int bfs() {

	q.emplace(n,0 );
	while (!q.empty())
	{
		int locate = q.front().first;
		int cost = q.front().second;
		q.pop();
		

		if (locate == k)
		{
			return cost;
		}

		int x1 = locate - 1;
		int x2 = locate + 1;
		int x3 = locate * 2;

		if (x1 >= 0 && !exCheck[x1])
		{
			exCheck[x1] = true;
			q.emplace( x1, cost + 1 );
		}
		if (x2 <MAX && !exCheck[x2])
		{
			exCheck[x2] = true;
			q.emplace(x2, cost + 1 );
		}
		if (x3 <MAX && !exCheck[x3])
		{
			exCheck[x3] = true;
			q.emplace( x3, cost + 1 );
		}

	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> n >> k;

	cout << bfs();
}