[BOJ]13549번 : 숨바꼭질 3 (c++)

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

13549번: 숨바꼭질 3

 

방법 1: bfs 이동횟수 메모이제이션, 덱 사용

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

using namespace std;

int bfs(int N, int K)
{
	int MAX = K * 2;
	// 이동횟수를 메모이제이션 할 time 벡터를 최대값으로 초기화
	vector<int> time(MAX + 1, numeric_limits<int>::max());
	
	// 순간이동과 걷기를 구분하기 위해 덱 선언
	deque<int> dq;
	
	// 덱에 시작위치 push, time[시작위치]를 0으로 초기화
	dq.push_back(N);
	time[N] = 0;

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

		// K에 도착하면 이동횟수 반환 및 종료
		if (now == K)
		{
			return time[now];
		}

		// 2배 순간이동, 뒤로 한칸 걷기, 앞으로 한칸 걷기 순으로 진행 (효율적)
		int next[] = { now * 2, now - 1, now + 1 };
		for (int i = 0; i < 3; ++i)
		{
			// 범위를 벗어나거나, 기존의 이동횟수가 새 이동횟수보다 같거나 작다면 pass
			if (next[i] < 0 || next[i] > MAX || time[next[i]] <= time[now])
			{
				continue;
			}

			// 2배 순간이동 일때
			if (i == 0)
			{
				/*
					현재 이동횟수 + 0, 덱의 앞으로 push
					--> 이동횟수가 적은 값부터 기록해주어야 함
				*/
				time[next[i]] = time[now];
				dq.push_front(next[i]);
			}
			// 걷기 일 때
			else
			{
				// 현재 이동횟수 + 1, 덱의 뒤로 push
				time[next[i]] = time[now] + 1;
				dq.push_back(next[i]);
			}
		}
	}
	return abs(N - K);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, K;
	cin >> N >> K;

	// K가 N보다 같거나 작으면 : 뒤로 걷기만 가능함.
	if (N >= K)
	{
		cout << N - K;
	}
	// K가 N보다 크면 : 너비우선 탐색으로 최소이동횟수 구하기
	else
	{
		cout << bfs(N, K);
	}

	return 0;
}

 

방법 2: bfs 이동횟수 메모이제이션, 큐 2개 사용

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

using namespace std;

int bfs(int N, int K)
{
	int MAX = K * 2;
	// 이동횟수를 메모이제이션 할 time 벡터를 최대값으로 초기화
	vector<int> time(MAX + 1, numeric_limits<int>::max());
	
	// 순간이동과 걷기를 구분하기 위해 2개의 큐 선언
	queue<int> q;
	queue<int> next_q;

	// 큐에 시작위치 push, time[시작위치]를 0으로 초기화
	q.push(N);
	time[N] = 0;

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

		// K에 도착하면 이동횟수 반환 및 종료
		if (now == K)
		{
			return time[now];
		}

		// 2배 순간이동, 뒤로 한칸 걷기, 앞으로 한칸 걷기 순으로 진행 (효율적)
		int next[] = { now * 2, now - 1, now + 1 };
		for (int i = 0; i < 3; ++i)
		{
			// 범위를 벗어나거나, 기존의 이동횟수가 새 이동횟수보다 같거나 작다면 pass
			if (next[i] < 0 || next[i] > MAX || time[next[i]] <= time[now])
			{
				continue;
			}

			// 2배 순간이동 일때
			if (i == 0)
			{
				/*
					현재 이동횟수 + 0, 현재 큐에 push
					--> 이동횟수가 적은 값부터 기록해주어야 함
				*/
				time[next[i]] = time[now];
				q.push(next[i]);
			}
			// 걷기 일 때
			else
			{
				// 현재 이동횟수 + 1, 다음 큐에 push
				time[next[i]] = time[now] + 1;
				next_q.push(next[i]);
			}
		}

		/*
			현재 큐가 비었다면 다음 큐와 swap
			(= 순간이동 작업 먼저, 걷기 작업을 나중에 수행하게 됨)
		*/
		if (q.empty())
		{
			q.swap(next_q);
		}
	}
	return abs(N - K);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, K;
	cin >> N >> K;

	// K가 N보다 같거나 작으면 : 뒤로 걷기만 가능함.
	if (N >= K)
	{
		cout << N - K;
	}
	// K가 N보다 크면 : 너비우선 탐색으로 최소이동횟수 구하기
	else
	{
		cout << bfs(N, K);
	}

	return 0;
}

 

방법 3: bfs 큐 2개 사용. <위치, 이동횟수>를 큐에 저장

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

using namespace std;

int bfs(int N, int K)
{
	int MAX = K * 2;
	vector<int> visit(MAX + 1);
	
	// <위치, 이동횟수> 
	// 순간이동과 걷기를 구분하기 위해 2개의 큐 선언
	queue<pair<int, int>> q;
	queue<pair<int, int>> next_q;

	// 큐에 {시작위치, 0 }push, 시작 위치 방문 체크
	q.push({N, 0});
	visit[N] = true;

	while (!q.empty())
	{
		int now = q.front().first;
		int time = q.front().second;
		q.pop();

		printf("now : %d  time : %d\n", now, time);

		// K에 도착하면 이동횟수 반환 및 종료
		if (now == K)
		{
			return time;
		}

		// 2배 순간이동, 뒤로 한칸 걷기, 앞으로 한칸 걷기 순으로 진행 (효율적)
		int next[] = { now * 2, now - 1, now + 1 };
		for (int i = 0; i < 3; ++i)
		{
			// 범위를 벗어나거나, 이미 방문한 적이 있는 위치면 pass
			if (next[i] < 0 || next[i] > MAX || visit[next[i]] == true)
			{
				continue;
			}

			visit[next[i]] = true;

			// 2배 순간이동 일때
			if (i == 0)
			{
				/*
					현재 큐에 <2배 위치, 현재 이동횟수> push
					--> 이동횟수가 적은 값부터 기록해주어야 하므로
				*/
				q.push({ next[i], time});
			}
			// 걷기 일 때
			else
			{
				// 다음 큐에 <+1/-1 위치, 현재 이동횟수 + 1> push
				next_q.push({ next[i], time + 1 });
			}
		}

		/*
			현재 큐가 비었다면 다음 큐와 swap
			(= 순간이동 작업 먼저, 걷기 작업을 나중에 수행하게 됨)
		*/
		if (q.empty())
		{
			q.swap(next_q);
		}
	}
	return abs(N - K);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, K;
	cin >> N >> K;

	// K가 N보다 같거나 작으면 : 뒤로 걷기만 가능함.
	if (N >= K)
	{
		cout << N - K;
	}
	// K가 N보다 크면 : 너비우선 탐색으로 최소이동횟수 구하기
	else
	{
		cout << bfs(N, K);
	}

	return 0;
}

 

 

BFS는 가중치가 없는 그래프일때 적합한 풀이인데, 

위 문제는 가중치가 각각 0, 1 이렇게 있다. 

따라서 BFS보다는 다익스트라가 더 적합한 풀이라고 한다.

하지만 나는 아직 다익스트라를 공부하지 않았기 때문에 일단 bfs로 풀었다.

다익스트라 풀이는 나중에 추가해야지

 

 

가중치 있는 그래프에는 적절하지 않은 bfs를 보완하는 방법은 2가지가 있다.

1. 큐를 2개 사용하여 우선순위를 분리하기 (방법 2, 3)

2. 덱을 사용하여 우선순위가 높은 작업을 push_front, 낮은 작업을 push_back하기 (방법 1)

 

 

 

1. 큐를 2개 사용하여 우선순위를 분리하기 (방법 2, 3)

 

작업에 따라서 각기 다른 큐에 push한다.

순간이동 작업은 현재 큐에, 걷기 작업은 다음 큐에 push한다

// 2배 순간이동 일때
if (i == 0)
{
    ...
    q.push(next[i]);
}
// 걷기 일 때
else
{
    ...
    next_q.push(next[i]);
}

 

현재 큐에 들어있는 작업(= 우선순위가 높은 작업)이 끝나면 

다음 큐와 swap한다. 포인터를 바꾸는 것이므로 시간복잡도에 영향을 주지 않는다.

if (q.empty())
{
    q.swap(next_q);
}

 

 

 

2. 덱을 사용하여 우선순위가 높은 작업을 push_front, 낮은 작업을 push_back하기 (방법 1)

 

순간이동 작업은 덱의 앞에, 걷기 작업은 덱의 뒤에 push한다.

// 2배 순간이동 일때
if (i == 0)
{
    ...
    dq.push_front(next[i]);
}
// 걷기 일 때
else
{
    ...
    dq.push_back(next[i]);
}

덱을 사용하면 해당 덱에 들어있는 작업만 관리하면 된다.