백준 그래프 1697번 숨박꼭질

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

1697번: 숨바꼭질

수빈이가 동생에게 도달하는 최소의 시간을 구하는 문제입니다. 해당 좌표까지 가는데 3가지 방법이 있는데 이는 x2, +1, -1이 있습니다. 

그래서 최소의 시간으로 도달할 수 있는  방법을 구하는 겁니다. 그래서 그래프 중에서도 최소의 시간으로 도달하기 위해 bfs를 사용하면 됩니다. 그래서 그래프 모양을 그려보면 아래와 같습니다. 

 

그래프

그리고 한번 방문했던 좌표는 다시 방문하지 않게 check해주어야 합니다. 

 

#include <cstdio>
#include <queue>
#include <utility>

using namespace std;

int map[300000];
queue <pair<int, int> > qu;

int N, K;

void bfs();
int isValidPoint(int point);
int isDestinationPoint(int point);

int main(){
	scanf("%d %d", &N, &K);
	bfs();
}

void bfs(){
	qu.push(make_pair(0, N));
	map[N] = 1;

	while(!qu.empty()){
		pair<int, int> previousPoint = qu.front();
		qu.pop();
		
		if(isDestinationPoint(previousPoint.second)){
			printf("%d", previousPoint.first);
			break;
		}

		int movePoint[3];
		movePoint[0] = previousPoint.second * 2;
		movePoint[1] = previousPoint.second + 1;
		movePoint[2] = previousPoint.second - 1;
		
		if(isValidPoint(movePoint[0])){
			qu.push(make_pair(previousPoint.first+1, movePoint[0]));
			map[movePoint[0]] = 1;
		}
		if(isValidPoint(movePoint[1])){
			qu.push(make_pair(previousPoint.first+1, movePoint[1]));
			map[movePoint[1]] = 1;
		}
		if(isValidPoint(movePoint[2]) && movePoint[2] >= 0){
			qu.push(make_pair(previousPoint.first+1, movePoint[2]));
			map[movePoint[2]] = 1;
		}
	}
}


int isValidPoint(int point){
	if(point <= 100000 && !map[point])
		return 1;
	else return 0;
}

int isDestinationPoint(int point){
	if(K==point)
		return 1;
	else return 0;
}