[백준 1697, 12851, 13549, 13913] 숨바꼭질1, 2, 3, 4

[백준 1697] 숨바꼭질

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

1697번: 숨바꼭질

#include <cstdio>
#include <queue>
int N, K;

struct _st
{
	int n;
	int t;
};

std::queue<_st> Q;
int visited[100000 + 2];

int BFS()
{
	//init
	Q.push({N, 0});
	visited[N] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		if (data.n == K) return data.t;

		//move
		int move[3] = { -1, 1, data.n };

		for (int p = 0; p < 3; p++) {
			int next = data.n + move[p];

			if (next < 0 || next > 100000) continue;
			if (visited[next]) continue;
			Q.push({next, data.t + 1});
			visited[next] = 1;
		}
	}
}




int main()
{
	scanf("%d %d", &N, &K);
	printf("%d\n", BFS());
	return 0;
}

x + 1, x - 1, 2 * x 로 움직일 때 모두 1초가 걸리므로 cost가 같다.

따라서 BFS + 큐 를 사용한다. 

---

[백준 12851] 숨바꼭질 2

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

12851번: 숨바꼭질 2

#include <cstdio>
#include <queue>
int N, K;
int time = 0x7fffffff;
int route;

struct _st
{
	int n;
	int t;
};
std::queue<_st> Q;
int visited[100000 + 2];

void BFS()
{
	Q.push({ N, 0 });
	visited[N] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		visited[data.n] = 1;

		if (data.t > time) return;

		if (data.n == K) {
			if (time > data.t) time = data.t;
			route++;
			continue;
		}

		// move 
		int move[3] = { 1, -1, data.n };

		for (int p = 0; p < 3; p++) {
			int next = data.n + move[p];
			if (next < 0 || next > 100000) continue;
			if (visited[next]) continue;

			Q.push({ next, data.t + 1 });
		}
	}
}

int main()
{
	scanf("%d %d", &N, &K);
	BFS();
	printf("%d\n%d\n", time, route);
}

중복 방문을 허용하여 최단 시간 안에 목적지에 방문하는 모든 경로의 수를 구해야하기 때문에 방문처리를 다음 노드에 대해서가 아닌(Q에 push할 때), 현재 노드에 대해서 한다(Q에서 pop할 때).

즉, 

방문했던 위치를 중복 방문하게 하려면 ?

=> 큐에 push할 때 방문처리 해주지 않고, pop 할 때 방문처리 한다. 

 

목적 위치에 도달하는 경로의 수를 알아내려면 ?

=> 목적 위치를 만들었다고 바로 return 하지 않고, 큐가 빌 때 까지 돌려준다. 

=> 한편 curr.time 이 ans 보다 큰 경우, 큐에 남아있는 데이터들 중 최단경로로 목적위치에 도달할 수 있는 것이 없으므로 break 하고 루프를 빠져나온다. 

---

[백준 13549] 숨바꼭질 3

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

13549번: 숨바꼭질 3

#include <cstdio>
#include <queue>
int N, K;

struct _st
{
	int n;
	int t;
};

struct COMP
{
	bool operator()(const _st &a, const _st &b) {
		return a.t > b.t;
	}
};

std::priority_queue<_st, std::vector<_st>, COMP> PQ;
int visited[100000 + 2];

int BFS()
{
	// init
	std::fill(visited, visited + 100001, 0x7fffffff);

	PQ.push({ N, 0 });
	visited[N] = 0;

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		if (data.n == K) return data.t;

		// move 
		int move[3] = { 1, -1, data.n };

		for (int p = 0; p < 3; p++) {
			int next = data.n + move[p];
			if (next < 0 || next > 100000) continue;
			
			if (p == 0 || p == 1) {
				if (visited[next] > data.t + 1) {
					PQ.push({ next, data.t + 1 });
					visited[next] = data.t + 1;
				}
			}	
			else if (p == 2 && visited[next] > data.t) {
				PQ.push({ next, data.t });
				visited[next] = data.t;
			}
		}
	}
}


int main()
{
	scanf("%d %d", &N, &K);
	printf("%d\n", BFS());
	return 0;
}

순간이동 할 때는 0초가 걸리므로, 각 노드까지 가는 cost가 다르다. 

따라서 우선순위 큐를 써서 해당 노드까지 가는데 걸린 시간이 가장 작은 것 부터 pop할 필요가 있다. 

이때 visited[next] <= data.t + 1(순간이동 할 경우는 visited[next] <= data.t) 이면 갱신해줄 필요가 없다. 이미 해당 노드에 도달한 적 있기 때문에 현재의 상태가 최적의 상태(최소 시간이 걸려서 해당 노드에 도달하는 상태)가 아니기 때문이다. 

따라서 이 경우는 배제하고, 무조건 현재 상태(data.t + 1, 순간이동의 경우 data.t)가 이전의 상태(visited[next])보다 작은 경우에만 상태발전을 위해 Q에 삽입해준다. 

---

[백준 13913] 숨바꼭질 4

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

13913번: 숨바꼭질 4

#include <cstdio>
#include <queue>
int N, K;

struct _st
{
	int n;
	int t;
};
std::queue<_st> Q;
int visited[100000 + 2];
int route[100000 + 2];

int BFS()
{
	Q.push({ N, 0 });
	visited[N] = 1;
	route[N] = -1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		if (data.n == K) return data.t;

		// move 
		int move[3] = { 1, -1, data.n };
		
		for (int p = 0; p < 3; p++) {
			int next = data.n + move[p];
			if (next < 0 || next > 100000) continue;
			if (visited[next]) continue;

			Q.push({ next, data.t + 1 });
			visited[next] = 1;
			route[next] = data.n;
		}
	}
}


void get_route(int node)
{
	if (route[node] == -1) {
		printf("%d ", node);
		return;
	}
	get_route(route[node]);
	printf("%d ", node);
}

int main()
{
	scanf("%d %d", &N, &K);
	printf("%d\n", BFS());
	get_route(K);
	return 0;
}

가장 처음 노드 표시하기 위해 route[N] = -1 넣어주었다. DFS 돌릴 때 리턴 조건으로 사용하기 위함이다. 

"route[다음노드] = 현재노드" 형태로 각 노드까지 최소 시간으로 가는 경로를 저장하였다.