BOJ 1261 알고스팟

www.acmicpc.net/problem/1261

1261번: 알고스팟

 

다익스트라와 BFS를 활용한 최단거리 찾기 문제였다.

이 문제는 다익스트라를 처음 배우고 풀어보려 했었는데 도저히 어떻게 풀어야 할지 몰라서 포기했는데

다익스트라를 좀 더 이해하고 보니 어떻게 활용해야 풀 수 있을지 알았다.

 

기존 다익스트라는 일차원 배열을 통해 한 노드에서 다른 모든 노드를 가는 최단거리를 구하지만

이번 문제에선 2차원 배열을 통해 각 배열의 최단거리를 구해준다.

 

입력은 %1d를 통해 받아줬고 다익스트라가 끝나면 d[m-1][n-1]을 출력하면 된다.

 

#include <iostream>
#include <queue>
using namespace std;

#define a first
#define b second
const int INF = 1e9;
priority_queue<pair<int, pair<int, int>>>pq;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int n, m;
int ar[101][101], d[101][101];
bool vis[101][101];

void dijkstra(int x, int y) {
	d[x][y] = 0;
	pq.push({ 0,{x,y} });
	vis[x][y] = true;

	while (!pq.empty()) {
		auto cur = pq.top().b; //위치를 pair로 받아줌
		int cost = -pq.top().a;
		pq.pop();
		if (d[cur.a][cur.b] < cost) continue; //현재 값보다 현재까지의 값이 크다면 pass
		for (int i = 0; i < 4; ++i) {
			int nx = cur.a + dx[i];
			int ny = cur.b + dy[i];
			if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
			if (vis[nx][ny]) continue; //방문했다면 pass
			vis[nx][ny] = true;
			if (ar[nx][ny] == 0) { //0 이라면 벽을 부수지 않으니 cost에 1을 더하지 않음
				pq.push({ -cost,{nx,ny} });
				d[nx][ny] = cost;
			}
			else {
				pq.push({ -(cost + 1),{nx,ny} });
				d[nx][ny] = cost + 1;
			}
			if (nx == m - 1 && ny == n - 1) return; //마지막 구간에 도달했다면 종료
		}
	}
}

int main() {
	cin >> n >> m;

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

	dijkstra(0, 0);

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

	return 0;
}