1261 : 알고스팟

풀이

다익스트라를 돌리면 된다!

굳이 최소 거리를 갱신하지 않은 이유는

priority queue에서 벽부숨(??)값이 가장 작은 노드부터 나오기 때문에

가장 먼저 (n, m)에 도착한 노드는 최단벽부숨(??)임이 보장된다.

이 성질이 생각보다 써먹을 데가 많다. (덕분에 코드가 짧아진다)

코드

#include <stdio.h>
#include <queue>
using namespace std;

const int dx[] = { 0,0,-1,1 };
const int dy[] = { -1,1,0,0 };
const int n_ = 100 + 5;

struct node { 
	int x, y, w;
	node(int x, int y, int w) : x(x), y(y), w(w) {}
	bool operator <(node A)const { return w > A.w; }
};

int main() {
	int n, m, chk[n_][n_] = { 0 };
	char a[n_][n_];
	priority_queue<node> pq;

	scanf("%d %d\n", &m, &n);
	for (int i = 0; i < n; i++) scanf("%s", a[i]);

	pq.push(node(0, 0, 0));
	while (!pq.empty()) {
		node top = pq.top();
		pq.pop();
		if (top.x == n - 1 && top.y == m - 1) {
			printf("%d", top.w);
			break;
		}
		chk[top.x][top.y] = true;
		for (int i = 0; i < 4; i++) {
			int nx = top.x + dx[i], ny = top.y + dy[i];
			int nw = top.w + (a[nx][ny] == '1' ? 1 : 0);
			if (nx < 0 || nx >= n || ny < 0 || ny >= m || chk[nx][ny]) continue;
			pq.push(node(nx, ny, nw));
		}
	}

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-03-14 09:11

Read more posts by this author