[백준 2917] 늑대 사냥꾼

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

2917번: 늑대 사냥꾼

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
int R, C;	// 행,열
char board[500 + 2][500 + 2];
int Dist[500 + 2][500 + 2];

int hx, hy;	// 현우좌표
int ox, oy;	// 오두막 좌표

struct _st
{
	int x, y;
	int dist;
};
std::vector<_st> V;
std::queue<_st> Q;
int visited[500 + 2][500 + 2];

struct COMP
{
	bool operator()(const _st &a, const _st &b)
	{
		return a.dist < b.dist;
	}
};
std::priority_queue<_st, std::vector<_st>, COMP> PQ;


void input()
{
	scanf("%d %d", &R, &C);
	for (int i = 0; i < R; i++) {
		scanf("%s", &board[i]);
		for (int j = 0; j < C; j++) {
			if (board[i][j] == '+') V.push_back({ i, j, 0 });
			else if (board[i][j] == 'V') {
				hx = i;
				hy = j;
				board[i][j] = '.';
			}
			else if (board[i][j] == 'J') {
				ox = i;
				oy = j;
				board[i][j] = '.';
			}
		}
	}
}

// 다익스트라 써도 되지만 안써도 된다. 
// 어차피 먼저 더 가까운 나무가 있었다면 먼저 도착해서 Dist 채워졌을 것임
void get_dist()	// 각 칸들과 나무 사이의 최단경로 구하기 
{
	// init
	memset(Dist, -1, sizeof(Dist));

	// dir
	int dir_x[4] = { 0, 0 ,1 ,-1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	for (_st v : V) {
		Q.push({ v.x, v.y, 0 });
		Dist[v.x][v.y] = 0;
	}

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

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (Dist[nx][ny] >= 0) continue;
			Q.push({ nx, ny, data.dist + 1 });
			Dist[nx][ny] = Dist[data.x][data.y] + 1;
		}
	}
}


int BFS()	// V -> J로 향하는데 각 칸마다 cost가 다르므로 우선순위 큐
{
	// init
	PQ = {};
	memset(visited, 0, sizeof(visited));

	// dir
	int dir_x[4] = { 0, 0 ,1 ,-1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	PQ.push({ hx, hy, Dist[hx][hy] });
	visited[hx][hy] = 1;
	int ans = Dist[hx][hy];


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

		if (ans > data.dist) ans = data.dist;

		if (data.x == ox && data.y == oy) return ans;

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (visited[nx][ny]) continue;
			PQ.push({ nx, ny,  Dist[nx][ny] });
			visited[nx][ny] = 1;
		}
	}
	return -1;
}



int main()
{
	input();
	get_dist();
	printf("%d\n", BFS());
	return 0;
}

이동 중 모든 칸에서 나무까지의 최단경로 다 구한 사람 naya na.. naya na....

언제쯤 효율적으로 생각할 수 있을까... 

 

이 문제는 늑대의 상태에 따라 나무와 해당 칸 까지의 정보가 변하는 것이 아니다. (저번주에 본 시험이 떠오르네요 ..^^..) 그래서 움직일 때 마다 나무까지의 거리를 구해줄 필요가 전혀 없고, 그냥 나무에서부터 각 칸 까지의 거리를 다 구해주면 된다. (BFS 돌리면 그게 최소 거리임)

 

그리고 늑대가 이동할 때 나무와 거리의 최솟값이 가장 큰 경로로 이동해야 하므로, 우선순위 큐를 사용하여 나무로부터의 거리가 큰 값(dist < a.dist)을 가진 칸 부터 우선적으로 방문하도록 구현했다. 

 

https://t-anb.tistory.com/47

백준 2917 늑대 사냥꾼

위에 분의 블로그를 보고 한번에 이해해버림.... 진짜 강추.. 

아 나는 아직도 BFS를 모르는건가..... 자괴감들어...