[백준 1697] 숨바꼭질

문제설명

해당 문제는 동생의 위치와 수빈이의 위치를 입력 받은 뒤 동생을 찾을 수 있는 가장 빠른 시간을 출력하면된다.

수빈이는 +1, -1, *2 로 매 초당 이동할 수 있다.

 

알고리즘

1. 수빈이와 동생의 위치를 입력받는다

2. 수빈이의 위치를 queue에 넣고 +1, -1, *2로 이동하였을 때 값이 지정범위를 벗어나는지, 방문한적 있는지 확인하고 조건에 맞는경우 queue에 넣는다

3. queue에서 front 값을 출력하여 도착지점에 도달하였는지 확인한다 -> 도달 시 반복문 탈출 

4. 매 연산이 끝날 때 마다 초를 증가 시킨다

코드

#include <iostream>
#include <stdio.h>
#include <queue>

using namespace std;
#define MAX 100001

bool visited[MAX];

int bfs(int n, int m) {
	queue<int> q; 
	int result = 0;
	q.push(n);//시작 지점 queue 에 넣기 

	while (1) {
		int size = q.size(); //현재 queue에 있는 수만 큼 반복 -> 계속 변함 
		
		for (int i = 0; i < size; i++)
		{
			int x = q.front();//맨 앞의 값 출력 
			q.pop();
			if (x == m)//위치에 도달했을 경우
				return result;//연산 중지 및 결과 반환

			if (x + 1 <= 100000 && visited[x+1] != true)//+1만큼 이동이 범위 이내, 방문 안함
			{
				visited[x + 1] = true;
				q.push(x + 1);
			}
			if (x - 1>=0 && visited[x-1] != true)//-1만큼 이동이 범위 이내이며, 방문 안함
			{
				visited[x - 1] = true;
				q.push(x - 1);
			}
			if (x*2 <= 100000 && visited[x*2] != true)//2배만큼 이동이 범위 이내이면서 ,방문안함
			{
				visited[x*2] = true;
				q.push(x*2);
			}
		}result++; 
	}

	return result; //결과 반환
}


int main() {
	cin.tie(0);
	cout.tie(0);

	int N, K;
	cin >> N >> K;
	cout<< bfs(N, K) << '\n';
}

고찰

이번 문제는 bfs알고리즘을 사용하여 최단 시간을 출력해야한다

queue를 사용하여 맨 앞의 값을 꺼내고 갈 수 있는 경우의 수를 모두 확인한다

그리고 가장 짧은 값을 출력시키는 문제였다