[백준/BOJ] 13549번: 숨바꼭질 3

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

13549번: 숨바꼭질 3

 

 

---

 

 

문제

---

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

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

 

입력

---

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

 

출력

---

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

 

예제 입력

---

5 17

 

예제 출력

---

2

 

코드 

---

BFS 풀이

1) 일반 queue 사용한 오답

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

#define MAX 100001
bool visited[MAX];
queue<pair<int, int>> q;
int res = MAX;

void dfs(int n, int k) {
	q.push({n, 0});

	while (!q.empty()) {
		int size = q.size();
		int flag = false;
		while (size--) {
			int front = q.front().first;
			int time = q.front().second;
			q.pop();
			if (visited[front]) continue;
			if (front == k) {
				if (res > time) res = time;
				flag = true;
			}
			visited[front] = true;

			if (front * 2 < MAX) q.push({ front * 2, time });
			if (front + 1 < MAX) q.push({ front + 1 , time + 1 });
			if (front - 1 >= 0) q.push({ front - 1, time + 1 });
		}
		if (flag) return;
	}
}

int main() {
	int n, k;
	cin >> n >> k;

	dfs(n, k);
	cout << res;
	return 0;
}

- 처음에 작성한 코드

- 문제점: 같은 좌표에 대해 시간이 적게 드는 순으로 정렬해주지 않아서 문제 발생. 이미 방문한 좌표라면 뒤에 같은 좌표에 대해 더 적은 시간이 들더라도 무조건 탐색하지 않음. 이 문제를 해결해보기 위해 코드 순서를 조금 바꿔보았으나 그냥 priority_queue를 쓰는게 훨씬 좋을듯..

 

2) 통과 코드_1

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

#define MAX 100001

bool visited[MAX];

int dfs(int n, int k) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({0, n});

	while (!pq.empty()) {
		int front = pq.top().second;
		int time = pq.top().first;
		pq.pop();

		if (visited[front]) continue;
		if (front == k) return time;
		visited[front] = true;

		if (front * 2 < MAX) pq.push({ time, front * 2 });
		if (front + 1 < MAX) pq.push({ time + 1, front + 1 });
		if (front - 1 >= 0) pq.push({ time + 1, front - 1 });
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, k;
	cin >> n >> k;

	cout << dfs(n, k);
	return 0;
}

- 코드 중복을 줄이려고 작성한 코드인데 큐에 일단 넣고 나서 방문 여부를 체크하기 때문에 시간 효율은 좋지 않은 것 같음. 

 

2) 통과 코드_2

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

#define MAX 100001

bool visited[MAX];

int dfs(int n, int k) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({0, n});
	visited[n] = true;

	while (!pq.empty()) {
		int front = pq.top().second;
		int time = pq.top().first;
		pq.pop();
		if (front == k) return time;
	

		if (front * 2 < MAX && !visited[front * 2]) {
			pq.push({ time, front * 2 });
			visited[front * 2] = true;
		}
		if (front + 1 < MAX && !visited[front + 1]) {
			pq.push({ time + 1, front + 1 });
			visited[front + 1] = true;
		}
		if (front - 1 >= 0 && !visited[front - 1]) {
			pq.push({ time + 1, front - 1 });
			visited[front - 1] = true;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, k;
	cin >> n >> k;

	cout << dfs(n, k);
	return 0;
}

- 대부분 이런식으로 작성한듯..! 내 코드보다 좀 더 빠름.

 

 

다익스트라 풀이

1) priority_queue 이용

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

#define MAX 100001

int dist[MAX];

void dijkstra(int n, int k) {
	fill_n(dist, MAX, MAX);
	dist[n] = 0;

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ dist[n], n });

	while (!pq.empty()) {
		int front = pq.top().second;
		int time = pq.top().first;
		pq.pop();
		//cout << "front: " << front << ", time: " << time << endl;
		if (time > dist[front]) continue;

		if (front * 2 < MAX && (dist[front * 2] > time)) {
			pq.push({ time, front * 2 });
			dist[front * 2] = time;
		}
		if (front + 1 < MAX && (dist[front + 1] > time + 1)) {
			pq.push({ time + 1, front + 1 });
			dist[front + 1] = time + 1;
		}
		if (front - 1 >= 0 && (dist[front - 1] > time + 1)) {
			pq.push({ time + 1, front - 1 });
			dist[front - 1] = time + 1;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, k;
	cin >> n >> k;

	dijkstra(n, k);
	cout << dist[k];
	return 0;
}

- 처음 다익스트라 구현방법을 공부할 때 우선순위 큐를 사용하는게 효율적이라고 해서 공부한대로 작성한 코드

인데..

 

2) queue사용

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

#define MAX 100001

int dist[MAX];

void dijkstra(int n, int k) {
	fill_n(dist, MAX, MAX);
	dist[n] = 0;

	queue<int> pq;
	pq.push(n);

	while (!pq.empty()) {
		int front = pq.front();
		pq.pop();

		if (front * 2 < MAX && (dist[front * 2] > dist[front])) {
			pq.push({ front * 2 });
			dist[front * 2] = dist[front];
		}
		if (front + 1 < MAX && (dist[front + 1] > dist[front] + 1)) {
			pq.push(front + 1);
			dist[front + 1] = dist[front] + 1;
		}
		if (front - 1 >= 0 && (dist[front - 1] > dist[front] + 1)) {
			pq.push(front - 1);
			dist[front - 1] = dist[front] + 1;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, k;
	cin >> n >> k;

	dijkstra(n, k);
	cout << dist[k];
	return 0;
}

- 우선순위 큐 말고 그냥 큐를 사용한 코드가 있어서 옹...? 하면서 코드를 수정해봤더니 훨씬 빨랐다....

- 복습할때 다시 보기로...!