BOJ 백준온라인져지 1261 알고스팟 풀이 Raw

분류가 다익스트라로 돼있어서 의문이 들었었다.

BFS 또는 DFS 면 되지 않을까??

질문 게시판을 가보니 BFS & Prirority queue 를 이용해서 최단거리를 구하는 것은 다익스트라다!

질문 게시판에서 솔루션은 얻었는데, 아이디어를 모르겠었다.

그래서 검색을 좀 하니까 바로 아이디어를 얻었다.

1. 도착지점에 도착할때, 가장 작은 가중치를 출력하라.

가장 작은 가중치를 출력할 때, Prioritiy queue 를 이용한다.

weight 를 기준으로 Priority queue 를 구성

2. 그러면 도착한 순간이 가장 작은 가중치를 갖게된다.

끝.

	#include <cstdio>
	#include <queue>
	#include <string.h>
	/**
	* https://www.acmicpc.net/problem/1261
	* BOJ 백준온라인져지 1261 알고스팟 풀이
	*/
	using namespace std;
	int xxxx[] = {0, 1, 0, -1};
	int yyyy[] = {-1, 0, 1, 0};
	struct node {
	int x, y, w;
	node (int x, int y, int w): x(x), y(y), w(w) {}
	bool operator < (node other) const {
	return w > other.w;
	}
	};
	int main () {
	int row, col;
	scanf("%d%d", &col, &row);
	bool visited[row][col];
	char map[row][col];
	for (int i = 0; i < row; i++) {
	scanf("%s", map[i]);
	}
	memset(visited, 0, sizeof(visited));
	priority_queue<node> pq;
	pq.push(node(0, 0, 0));
	while(pq.size()) {
	node n = pq.top(); pq.pop();
	int cx = n.x; int cy = n.y; int cw = n.w;
	if (cx == row - 1 && cy == col - 1) {
	printf("%d", cw);
	break;
	}
	visited[cx][cy] = true;
	for (int i = 0; i < 4; i++) {
	int nx = cx + xxxx[i]; int ny = cy + yyyy[i];
	if (visited[nx][ny] || nx < 0 || ny < 0 || nx >= row || ny >= col) continue;
	int nw = cw + map[nx][ny] - 48;
	pq.push(node(nx, ny, nw));
	}
	}
	}

view raw BOJ_1261.cpp hosted with ❤ by GitHub