[BOJ] 1261번 알고스팟 (C++)

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

1261번: 알고스팟

 

#include <iostream>
#include <queue>
#define INF 987654321
using namespace std;

int M, N;
int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int arr[101][101];
int dist[101][101];

void dijkstra() {
    queue<pair<int, int>> pq;
	pq.push({ 0, 0 });
	dist[0][0] = 0;

	while (!pq.empty()) {
		int cy = pq.front().first;
		int cx = pq.front().second;
		pq.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + dy[i];
			int nx = cx + dx[i];
            
			if (!(ny >= 0 && ny < N && nx >= 0 && nx < M)) continue;

			if (arr[ny][nx] == 1) {
				if (dist[ny][nx] > dist[cy][cx] + 1) {
					dist[ny][nx] = dist[cy][cx] + 1;
					pq.push({ ny,nx });
				}
			}else if (arr[ny][nx] == 0) {
				if (dist[ny][nx] > dist[cy][cx]) {
					dist[ny][nx] = dist[cy][cx];
					pq.push({ ny,nx });
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	scanf("%d %d", &M, &N);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &arr[i][j]);
			dist[i][j] = INF;
		}
	}

	dijkstra();
	printf("%d", dist[N - 1][M - 1]);
	return 0;
}

 

숫자가 아닌 문자열로 주어졌으므로 scanf로 한 글자씩 입력받았다.

거리 배열을 2차원 배열로 선언하고, 칸의 값이 1일 때와 0일 때를 구분하여 가중치를 업데이트한다.