[BOJ]백준 2917번: 늑대 사냥꾼(C++)/Dijkstra

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

2917번: 늑대 사냥꾼

다익스트라를 이용해서 풀었지만 거리의 누적 합의 최소를 찾는 것이 아닌 경로 중 최소값 만을 요구하는 문제였다

그래서 맨 처음 입력을 받은 뒤 모든 나무의 좌표를 큐에 넣은 뒤 BFS를 수행하여 모든 정점으로부터 나무까지의 거리를 구했고

다익스트라를 수행하면서 선택할 수 있는 다음 좌표 중 (나무와의 거리)가 가장 큰 좌표를 선택하게 했다

 

시간초과가 엄청 많이 났는데 .. 그 이유는 무식하게 모든 나무 좌표마다 BFS를 새로 돌리려고 해서 ㅠ

그냥 큐에 한번에 넣어주고 시작하면 됐는데 .. BFS 까먹은 티 너무 많이 났다

테스트 케이스 링크

위의 링크 - CONTEST #2 - Test data - official_testdata - vuk 에 있는 반례를 참고해서 풀었다

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#define pip pair<int,point>
#define INF 987654321
using namespace std;

typedef struct { int x, y; }point;

vector<string> board;
bool visit[501][501];
int treeDist[501][501], dist[501][501];
int n, m, dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
point s, f,pre[501][501];

bool safe(int x, int y) { return x >= 0 && x < m&& y >= 0 && y < n; }

typedef struct {
	bool operator() (pip a, pip b) { return a.first < b.first; }
}cmp;

void bfs() {
	memset(visit, false, sizeof visit);
	queue<point> q;

	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if (board[i][j] == '+') {
				q.push({ j,i });
				visit[i][j] = 1;
				treeDist[i][j] = 0;
			}

	for (int time = 0;; time++) {
		int size = q.size();
		if (!size)break;

		while (size--) {
			point cur = q.front(); q.pop();
			treeDist[cur.y][cur.x] = time;

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i], ny = cur.y + dy[i];
				if (!safe(nx, ny) || visit[ny][nx])continue;
				if (treeDist[ny][nx] > time) {
					q.push({ nx,ny });
					visit[ny][nx] = 1;
				}
			}
		}
	}
}

int dijkstra(int x, int y) {
	priority_queue<pip, vector<pip>, cmp> pq;
	point p = { x,y };
	int ans = min(treeDist[s.y][s.x],treeDist[f.y][f.x]);

	memset(visit, false, sizeof visit);
	pq.push(make_pair(treeDist[y][x], p));

	while (!pq.empty()) {
		point cur = pq.top().second; 
		int cost = pq.top().first;	pq.pop();

		if (visit[cur.y][cur.x])continue;
		ans = min(ans, cost);
		visit[cur.y][cur.x] = true;

		if (cur.x == f.x && cur.y == f.y)break;
		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i], ny = cur.y + dy[i];
			if (!safe(nx, ny)||visit[ny][nx])continue;

			point next = { nx,ny };
			pq.push(make_pair(treeDist[ny][nx], next));
		}
	}

	return ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	fill(&treeDist[0][0], &treeDist[n][m + 1], INF);

	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		board.push_back(s);
	}

	bfs();
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 'V')s = { j,i };
			if (board[i][j] == 'J')f = { j,i };
		}
	cout << dijkstra(s.x, s.y);
	return 0;
}