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

정도영·2022년 3월 4일

Baekjoon

목록 보기

3/4

⬇️ 문제 출처

💡 접근 방법

단순 BFS? 로 알았던 내 자신 머리 박아.
맞왜틀을 시전했던 나는 질문 검색을 보고 순간이동을 하는 경우에는 0초 후에 위치로 이동하므로 단순히 동생의 위치에 도달했다고 출력하는 것이 아니라는 것을 알았다.
걸어서 이동 후에 순간이동으로 이동할 수 있는 모든 위치를 간 후에, 만약 동생의 위치가 있다면 출력하고 없다면 다음 위치로 걸어서 가는 것을 구현했다.

✏️ 풀이

수빈이의 위치를 queue에 넣어주고, 순간이동해서 갈 수 있는 모든 점을 queue에 넣어준다. 갈 수 있는 점에 동생에 위치가 있으면 그 때의 시간을 출력하고, 아니라면 다음 걸어서 갈 수 있는 위치를 큐에 넣고 반복해줬다.

⌨️ 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <string>
#include <queue>
#include <cstring>
#include <tuple>
#include <cmath>
#include <math.h>
#define MAX_N 1000+5
#define endl "\n"
const int INF = 987654321;
typedef long long ll;
using namespace std;
bool visited[100000 + 5];
int N, K;

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> K;
	queue<pair<int, int>> q;
	q.push({N,0});
	while (!q.empty()) {
		int now = q.front().first;
		int time = q.front().second;
		q.pop();

		if (now == K) {
			cout << time;
			return 0;
		}

		if (now != 0) {
			for (int i = now; i <= 100000; i *= 2) {
				if (!visited[i]) {
					q.push({ i,time });
					visited[i] = true;
				}
			}
		}
		
		if (now - 1 >= 0) {
			if (!visited[now - 1]) {
				q.push({ now - 1,time + 1 });
				visited[now - 1] = true;
			}
		}
		if (now + 1 <= 100000) {
			if (!visited[now + 1]) {
				q.push({ now + 1,time + 1 });
				visited[now + 1] = true;
			}
		}
	}

	return 0;
}

+ 추가

다른사람들의 코드를 보다가 deque을 사용해서 0-1 BFS 라는 것을 사용한 것을 보고 문득, deque과 0-1 BFS가 궁금해져서 알아봤다.

deque?

우리가 흔히 아는 queue, stack과 비슷한 데 deque는 특이하게 데이터의 삽입과 삭제가 front와 back에서 둘 다 가능하다. 또한, Vector or Array와 같이 인덱스로도 접근이 가능하다!
But, Vector와의 차이점은 컨테이너 처음부터 끝까지 연속 메모리 공간이 아니다!
0-1 BFS?

BFS는 BFS인데 특수한 환경에서 작동할 수 있는 BFS이다. 그 특수한 환경이 뭐냐고?

0-1 BFS는 가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾고자 할 때 BFS를 응용하여 풀 수 있게 된다.

1. 덱의 front에서 현재 노드를 꺼낸다.
2. 연결된 인접 노드를 살펴본다.
3. 현재 노드까지 소비된 비용 + 그 노드를 향하는 가중치 < 그 노드까지 가는데 소비된 비용이면 소비된 비용을 갱신해준다.
4. 노드가 갱신된 상태에서 만약 그 노드를 향하는 가중치가 0이면 덱의 front, 1이면 덱의 back에 삽입하도록 한다.
5. 덱에서 더 이상 꺼낼 노드가 없을 때까지 위 과정을 반복한다.

⌨️ 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <string>
#include <queue>
#include <cstring>
#include <tuple>
#include <cmath>
#include <math.h>
#define MAX_N 1000+5
#define endl "\n"
const int INF = 987654321;
typedef long long ll;
using namespace std;
bool visited[200000 + 5];

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int N, K;
	cin >> N >> K;
	deque<pair<int,int>> dq;
	dq.push_front({ N,0 });
	visited[N] = true;

	while(!dq.empty()){
		int now = dq.front().first;
		int time = dq.front().second;
		dq.pop_front();
		
		if (now == K) {
			cout << time;
			return 0;
		}

		if (now * 2 <= 100000 && !visited[now * 2]) {
			visited[now * 2] = true;
			dq.push_front({ now * 2, time });
		}
		if (now + 1 <= 100000 && !visited[now + 1]) {
			visited[now + 1] = true;
			dq.push_back({ now + 1, time + 1});
		}
		if (now - 1 >= 0 && !visited[now - 1]) {
			visited[now - 1] = true;
			dq.push_back({ now - 1,time + 1 });
		}
	}
}