[C++]백준 - 1697번 문제

1697번: 숨바꼭질 (acmicpc.net)

1697번: 숨바꼭질

 

1697번 : 숨바꼭질

---

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

입력

---

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

 

출력

---

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

 

 

---

 

생각해 볼 점

---

간단한 BFS 문제입니다.

 

N, K를 입력받고, N의 위치에서 탐색을 시작해 K에 도달하면 됩니다.

 

BFS이므로 큐를 사용하고, 큐에 N을 집어 넣습니다.

 

그리고 Visited 배열을 사용해서, 이미 갔던 장소인지 확인합니다.

Visited[N] = true인 채로 탐색을 시작합니다.

 

탐색이 한 번 진행 할 때, 탐색 횟수를 1 증가시키고, 큐의 모든 내용물을 꺼내 탐색을 진행합니다.

 

예를 들어, N번 째 좌표에서 탐색은 N + 1, N - 1, N * 2의 좌표를 탐색합니다.

 

탐색 : N -> Queue{N + 1, N - 1, N * 2}

 

다음 좌표들이 유효하다면(좌표들이 0 이상, 100000 이하일 것), 좌표들을 큐에 집어넣습니다.

 

탐색을 반복하여 K에 도달하게 되면, 탐색을 끝내고 탐색 횟수를 출력합니다.

 

코드

---

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() 
{
	int N, K;
	bool visited[100001] = {false,};
	queue<int> q;
	
	cin >> N >> K;
	
	q.push(N);
	visited[N] = true;
	int result = 0;
	
	//BFS 탐색
	while(!q.empty() && !visited[K])
	{
	    result++;
	    vector<int> des;
	    
    	while(!q.empty())
    	{
    	    int current = q.front();
    	    q.pop();
    	    
    	    //다음 탐색의 위치
    	    int check[3] = {current - 1, current + 1, current * 2};
    	    
    	    for(int next : check)
    	    {
    	        //다음 탐색의 조건을 체크
    	        if(0 <= next && next < 100001 && !visited[next])
    	        {
    	            des.push_back(next);
    	            visited[next] = true;
    	        }
    	    }
    	}
    	for(int next : des) q.push(next);
	}
	
	cout << result;
	return 0;
}

 

그 외

---