[BFS] 백준 13549 - 숨바꼭질3

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

13549번: 숨바꼭질 3

숨바꼭질 3 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

41334

12134

7707

25.826%

문제

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

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

입력

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

출력

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

예제 입력 1 

5 17

예제 출력 1 

2

 

---

순간이동을 하는 경우 0초가 소모된다는 점에서 이전 문제와 차이점을 보인다.

https://it-sounds-like-coding.tistory.com/20 << 여기서 풀었던 것에, 순간이동을 할 경우 0초가 걸리는 것으로 조금 수정을 해봤지만 정답이 아니었다. 그래서 고민을 좀 하게 됐다.

지금까지 bfs를 풀 때, 우선순위가 높고 소모되는 시간이나 거리가 0이면 가장 먼저 queue에 삽입해야했다. 이 점을 잊고 있었다. 그렇다면 순간이동을 할 경우엔 너비 탐색하는 우선순위가 높고, 아닐 경우엔 낮은 것이다.

 

• 순간이동하는 경우엔 queue의 맨 앞에, 아닌 경우엔 맨 뒤에 들어가야 한다.

여기서 새로운 컨테이너를 꺼냈다. deque.

deque은 스택이나 큐 처럼 한 방향에서만 삽입이나 삭제가 이루어지는 컨테이너가 아니다. 양방향으로 삽입과 삭제가 가능하다.

순간이동하면 deque에 push_front, 그 외 이동이면 push_back을 해줬다.

 

• 다익스트라 알고리즘과 유사하다!

다익스트라 알고리즘은 방문하지 않은 정점 중 가장 가중치가 낮은 정점을 방문한다.

위의 코드대로라면 순간이동한 경우부터 방문하게 되니까, 다익스트라 알고리즘과 유사하다.

 

#include <iostream>
#include <vector>
#include <deque>

#define SIZE 100001
#define endl '\n'

using namespace std;

int N, K; // 수빈이의 위치, 동생의 위치
int visited[SIZE]; // 방문여부 체크
int moveTime[SIZE]; // 도착하는데 걸린 시간


void bfs(int start)
{
	deque<int> bfsd;
	visited[start] = true;
	bfsd.push_front(start);
	int next[3];

	while (!bfsd.empty())
	{
		int now = bfsd.front();
		bfsd.pop_front();

		if (now == K)
			return;

		next[0] = now * 2;
		next[1] = now + 1;
		next[2] = now - 1;

		for (int i = 0; i < 3; ++i)
		{
			if (next[i] >= SIZE || next[i] < 0) // 칸이 유효한지 확인
				continue;

			if (!visited[next[i]]) // 방문한 적 없음
			{
				visited[next[i]] = true;
				if (i != 0)
				{
					moveTime[next[i]] = moveTime[now] + 1;
					bfsd.push_back(next[i]);
				}
				else // 순간이동
				{
					moveTime[next[i]] = moveTime[now];
					bfsd.push_front(next[i]);
				}
			}
		}
	}
}

int main()
{
	cin >> N >> K;

	bfs(N);
	cout << moveTime[K] << endl;
}