[BOJ] 알고스팟

[BOJ] 알고스팟

Problem URL : 알고스팟

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

using namespace std;

int C, R;
int map[101][101];
int dist[101][101];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> C >> R;
	string row;
	for (int i = 0; i < R; i++) {
		cin >> row;
		for (int j = 0; j < C; j++) {
			dist[i][j] = 987654321;
			map[i][j] = row[j] - '0';
		}
	}
	queue<pair<int, int>> q;
	q.push({ 0,0 });
	dist[0][0] = 0;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
			if (dist[nx][ny] > dist[x][y] + map[nx][ny]) {
				dist[nx][ny] = dist[x][y] + map[nx][ny];
				q.push({ nx,ny });
			}
		}
	}

	cout << dist[R - 1][C - 1] << "\n";
	return 0;
}

Comments

map 각 지점까지의 거리를
도달하기까지 부순 벽의 개수로 해서 BFS를 해주면 된다.