[백준/C++] 1261번: 알고스팟

문제

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

1261번: 알고스팟

---

문제 요약

N × M 크기의 미로에서 (1, 1)에서 출발해 (N, M)까지 가기 위해 벽을 최소 몇 개 부수어야하는지 출력한다.

 

어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다.

---

코드

#include<iostream>
#include<queue>
#include<algorithm>
#include<tuple>

using namespace std;

#define MAX 100

int n, m;

int board[MAX][MAX];
int dist[MAX][MAX]; // (0, 0)에서 (i, j)까지 이동하는데 제거해야하는 1의 최소 개수
bool visit[MAX][MAX];

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

queue<tuple<int, int>> q;

int res = 1e9;
int cnt;

void dijstra() {
	visit[0][0] = true;
	dist[0][0] = 0;
	q.push({ 0, 0 });
	while (!q.empty()) {
		int x, y;
		tie(x, y) = q.front();
		q.pop();

		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (board[nx][ny] == 1) {
				if (dist[nx][ny] > dist[x][y] + 1) { // 아직 dist[nx][ny]가 최소가 아닐 때
					dist[nx][ny] = dist[x][y] + 1;
					q.push({ nx, ny }); // 주변 노드도 새롭게 갱신
				}
			}
			else {
				if (dist[nx][ny] > dist[x][y]) {
					dist[nx][ny] = dist[x][y];
					q.push({ nx, ny });
				}
			}
		}
	}
}

int main() {
	cin >> m >> n;
	//cout << "check";
	string str;
	for (int i = 0; i < n; i++) {
		cin >> str;
		for (int j = 0; j < m; j++) {
			board[i][j] = str[j] - '0';
			dist[i][j] = 1e9;
		}
	}

	dijstra();

	cout << dist[n - 1][m - 1];

	return 0;
}

---

코드 설명

1. 미로의 크기 정보와, 각 칸의 빈 방 여부를 입력 받는다.

 

2. 다익스트라 알고리즘을 이용해 (1, 1)부터 각 칸까지 벽을 최소 몇 개를 부수어야 도착하는지 dist 배열에 저장한다.

 

2 - 1. 각 칸을 방문할 때, 빈 방인지, 벽이 존재하는지에 따라 나눠 dist를 갱신한다.

 

2 - 2. 벽이 존재한다면, 해당 칸의 벽을 부수어야하므로, 이전 dist + 1과 비교하여 작은 값으로 갱신한다.

 

2 - 3. 빈 방이라면, 이전 칸에서 벽을 부수지 않고 이동할 수 있으므로, dist와 비교하여 작은 값으로 갱신한다.

 

2 - 4. 해당 칸이 갱신되었다면, 큐에 인덱스 정보를 넣어 주변 칸의 dist도 갱신한다.

 

3. dist[n-1][m-1]을 출력한다.