[백준] 1261번: 알고스팟

www.acmicpc.net/problem/1261

1261번: 알고스팟

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

using namespace std;

const int MAX = 10000;
const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };
typedef pair<int, int> P;

int dist[100][100];

struct cmp {
	bool operator()(P a, P b) {
		return dist[a.first][a.second] > dist[b.first][b.second];
	}
};

int main() {
	int m, n;
	int miro[100][100];
	scanf("%d %d", &m, &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &miro[i][j]);
		}
	}
	bool visited[100][100] = { 0, };

	priority_queue<P, vector<P>, cmp> pq;

	fill(&dist[0][0], &dist[99][99] + 1, MAX);
	dist[0][0] = 0;

	pq.push(P(0, 0));

	while (!pq.empty()) {
		int x = pq.top().first;
		int y = pq.top().second;

		if (visited[x][y]) {
			pq.pop();
			continue;
		}

		visited[x][y] = true;
		pq.pop();

		for (int i = 0; i < 4; i++) {
			int nextX = x + dx[i];
			int nextY = y + dy[i];
			if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m) continue;

			if (!visited[nextX][nextY] && dist[x][y] + miro[nextX][nextY] < dist[nextX][nextY]) {
				dist[nextX][nextY] = dist[x][y] + miro[nextX][nextY];
				pq.push(P(nextX, nextY));
			}
		}
	}

	printf("%d", dist[n - 1][m - 1]);
}

 

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

using namespace std;

const int MAX = 10000;
const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };
typedef pair<int, int> P;

int main() {
	int m, n;
	int miro[100][100];
	scanf("%d %d", &m, &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &miro[i][j]);
		}
	}

	int dist[100][100];
	fill(&dist[0][0], &dist[99][99] + 1, MAX);
	dist[0][0] = 0;

	queue<P> q;
	q.push(P(0, 0));

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (dist[x][y] + miro[nx][ny] < dist[nx][ny]) {
				dist[nx][ny] = dist[x][y] + miro[nx][ny];
				q.push(P(nx, ny));
			};
		}
	}
    
	printf("%d", dist[n - 1][m - 1]);
}

 

위에꺼는 다익스트라, 아래꺼는 BFS + 메모이제이션 이라고 생각하는데.. 맞나?

나중에 시간날 때 시간복잡도도 계산해봐야겠다.