[ 백준 13549] 숨바꼭질3 (C++)

 

 

 

13549번: 숨바꼭질 3

 

 

문제!

---

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

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

 

---

 

요약하면 동생이 K위치에 있으면

수빈이가 N 에서 3가지 이동방식 ( N+1 , t+1), ( N-1 , t+1), ( N*2 , t)을 이용해  K에 도달하는 최소 시간을 출력하는 문제!

 

 

문제는 단순히 N의 위치에서 3가지 이동방식중 하나씩 골라 이동시켜 주는 

굉장히 단순한 탐색 문제... 인줄 알았으나

 

 

Bfs로 구현한 코드는 바로 실패...

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <deque>
#include <queue>
#include <deque>


using namespace std;

int N, K;
int answer = 987654321;

int visit[100001] = { 0 };

queue<int> Templist; // 위치

void Bfs(int location) { // 순간이동 하거나 1칸이동하는거 2가지의 경우 밖에 없다!
	
	
	Templist.push(location);//초기값
	visit[location] = 1;

	while (!Templist.empty()) {
		int temp = Templist.front();
		Templist.pop();
		
		if (temp == K) {
			answer = visit[K]-1;
			return;
		}

		//+1
		if (temp + 1 < 100001) {
			if (!visit[temp + 1]) {
				Templist.push( temp + 1);
				visit[temp + 1] = visit[temp]+1;
			}
		}

		//-1
		if (temp - 1 >= 0) {
			if (!visit[temp - 1]) {
				Templist.push( temp - 1 );
				visit[temp- 1] = visit[temp] + 1;
			}
		}

		// *2
		if (temp * 2 < 100001) {
			if (!visit[temp * 2]) {
				Templist.push(temp * 2);
				visit[temp * 2] = visit[temp];
			}
		}
	}
	return;
}

// 그냥이동 1초후 X-1, X+1   || 순간이동 0초후 2*X 로 이동 
int main() {
	cin >> N >> K;

	Bfs(N);

	cout << answer << "\n";
	return 0;
}

 

틀린 부분이 없다고 생각된 와중 찾게 된 글에서 해답을 찾을 수 있었습니다. 

글 읽기 - [13549-숨바꼭질3] BFS 큐에 넣는 순서 질문

답변의 핵심은

거리가 *2될때 t가 늘어나지 않는 경우

거리가 +1될때 t가 +1 되는 경우 

 

 

각각의 경우가 동일한 부분이 없기에

어떤 경우를 먼저 실행하는지 순서에 따라 bfs가 틀릴 수도 있다!

 

 

그렇기에 경우에 따른 우선순위가 필요하다

+++++ 우선순위..... 단순 bfs 가 아님!

 

 

 

순서는 t+1 되는 경우는 상관 없지만 

t가 늘어나지 않는 *2의 경우를 항상 먼저 실행해야 한다고 합니다. 

 

 

 

 

 

그러기 위해선 2가지 방법으로 풀어낼 수 있다고 합니다. 

1. 덱을 이용한 우선순위 bfs

2. 다익스트라 알고리즘

 

시간을 저장한 순간 사실상 동일....

 

 

 

 

 

코드!

---

 

 

코드 자체는 위에서 구현한(실패 코드) 의 bfs와 다르지 않았습니다. 

 

 

먼저 아래처럼 기존 코드에서 queue 를 deque로 바꿔주었습니다. 

void Bfs(int location) { // 순간이동 하거나 +-1칸이동하는거 3가지의 경우 밖에 없다!
	deque<int> Templist;
	
	Templist.push_back(location);//초기값
	visit[location] = 1;

	while (!Templist.empty()) {
		int temp = Templist.front();
		Templist.pop_front();
		
		if (temp == K) {
			answer = visit[K]-1;
			return;
		}

 

그리고 *2 경우는 push_front를 이용하여 항상 처음 실행하도록 만들어 주었고 

나머지는 push_back을 이용해 일반적인 bfs로 동작하게끔 구성해 줍니다. 

// *2
		if (temp * 2 < 100001) {
			if (!visit[temp * 2]) {
				Templist.push_front(temp * 2);
				visit[temp * 2] = visit[temp];
			}
		}
        
		//-1
		if (temp - 1 >= 0) {
			if (!visit[temp - 1]) {
				Templist.push_back( temp - 1 );
				visit[temp- 1] = visit[temp] + 1;
			}
		}

		//+1
		if (temp + 1 < 100001) {
			if (!visit[temp + 1]) {
				Templist.push_back(temp + 1);
				visit[temp + 1] = visit[temp] + 1;
			}
		}

 

이렇게 되면 항상 *2를 최대한 많이 실행한 상태에서!

+1과 -1을 실행하고 최소 시간을 구할수 있도록 구성되는 것입니다. 

 

 

단순히 3경우가 동일한 방법이라고 생각했었는데 아니였네요;;; 

 

 

 

다익스트라 알고리즘으로 구현하고 싶다면

위 Bfs코드에서는 visit에 방문처리만 해주겠지만 

 

 

아래처럼 크기 비교가 들어간 순간 다익스트라로 구현했다고 볼 수 있겠죠!

if(visit[temp + 1] > visit[temp] + 1)

 

이 정도 차이 밖에 없네요..?

 

 

 

 

---

 

이번 문제는 어려운 부분이 많았네요..

*2배를 먼저 해주고 queue를 사용할 수 도 있지만 deque를 통해 확실하게 푸는 것이 정답에 가깝다...

 

 

넵..

 

 

 

 

이번 문제를 통해 배운 내용

1. 무작정 bfs를 하기위해서는 이동조건이 같아야 한다.

  >> 다를 시 우선순위를 확인해 보아야 합니다. 

 

2. deque를 통해 우선순위를 조절할 수 또 있다.

 

3. 다익스트라와 bfs는 거리를 저장유무 말고는 비슷하다

 

 

 

 

 

 

 

 

 

ALL

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <deque>
#include <queue>
#include <deque>


using namespace std;



int N, K;
int answer = 987654321;

int visit[100001] = { 0 };



 /// 덱을 사용하는 이유.....   >> 우선순위...


void Bfs(int location) { // 순간이동 하거나 +-1칸이동하는거 3가지의 경우 밖에 없다!
	deque<int> Templist;
	
	Templist.push_back(location);//초기값
	visit[location] = 1;

	while (!Templist.empty()) {
		int temp = Templist.front();
		Templist.pop_front();
		
		if (temp == K) {
			answer = visit[K]-1;
			return;
		}


		// *2
		if (temp * 2 < 100001) {
			if (!visit[temp * 2]) {
				Templist.push_front(temp * 2);
				visit[temp * 2] = visit[temp];
			}
		}


		

		//-1
		if (temp - 1 >= 0) {
			if (!visit[temp - 1]) {
				Templist.push_back( temp - 1 );
				visit[temp- 1] = visit[temp] + 1;
			}
		}

		//+1
		if (temp + 1 < 100001) {
			if (!visit[temp + 1]) {
				Templist.push_back(temp + 1);
				visit[temp + 1] = visit[temp] + 1;
			}
		}
		
	}

	return;
}




// 그냥이동 1초후 X-1, X+1   || 순간이동 0초후 2*X 로 이동 
int main() {
	cin >> N >> K;

	Bfs(N);

	cout << answer << "\n";
	return 0;
}

 

 

 

 

틀린 점이 있다면 댓 달아주세요!