백준 1697 숨바꼭질 (C++)

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

dp 문제라고 생각하고 풀다가 답이 안나와서 분류를 봤다.

bfs로 풀 수 있는 문제였다.

이런느낌으로 연결된 그래프를 연상했다.

dfs로 사용하면 모든 경우를 끝까지 가봐서 가장 작은 것을 선택 해야 겠지만

bfs를 사용 시에 같은 횟수로 먼저 도착했을 때 가장 최소 비용을 사용했다고 확인할 수 있으니 bfs를 사용.

#include <iostream>
#include <algorithm>
#include <vector>
#include<cstring>
#include<queue>
#include<cmath>
struct forq {
	int num;
	int count;
};
using namespace std;
bool check[100005];
int linenum, verticenum;
int subin, sister;
void bfs(int start);
int main()
{
	cin >> subin >> sister;
	memset(check, 0, sizeof(check));
	bfs(subin);
}
void bfs(int start)
{
	queue<forq> q;
	q.push({ start,0 });
	check[start] = 1;
	while (!q.empty())
	{
		forq temp = q.front();
		if (temp.num == sister)
		{
			cout << temp.count;
			return;
		}
		q.pop();
		if (temp.num - 1 >= 0 && check[temp.num-1]==0 )
		{
			q.push({ temp.num - 1,temp.count + 1 });
			check[temp.num-1] = 1;
		}
		if (temp.num + 1 <= 100000 && check[temp.num + 1] == 0)
		{
			q.push({ temp.num +1 ,temp.count + 1 });
			check[temp.num + 1] = 1;
		}
		if (temp.num * 2 <= 100000 && check[temp.num * 2] == 0)
		{
			q.push({ temp.num * 2,temp.count + 1 });
			check[temp.num *2] = 1;
		}

	}
}

 

처음에는  main에서 모든 정점에 대해 +1, -1, *2가 가능 하다면 인접리스트로 모든 간선을 넣어 주었지만

그렇지 않아도 해결할 수 있는 상황이 더 효율적이었기에 위와 같이 구현했다.