[백준][Gold 4][C++] 1261 알고스팟

문제

백준 -  1261 알고스팟 (Gold 4)

1261번: 알고스팟

 

---

문제 풀이

접근 방식

이 문제는 0, 0에서 시작하여 N-1, M-1에 도달하기 위해 파괴한 벽의 개수의 최솟값을 구하는 문제이다.

그래서 BFS + DP의 방식으로 이 문제를 해결하였다.

 

우선, destroy라는 2차원 벡터의 모든 값들을 큰 수(987654321)로 설정해놓고,BFS 탐색을 수행하며 그 위치에 도달하기 위해 파괴한 벽의 개수의 최솟값을 destroy 벡터에 저장해주었다.

 

즉, 큐를 이용하여 0,0에서부터 상하좌우 네 방향을 탐색하였고,

이동 가능한 위치인 map[nx][ny]의 값이 0인 경우에는 (벽을 안 부숴도 되는 경우)

destroy[x][y]과 destroy[nx][ny]을 비교하여 더 작은 값을 destroy[nx][ny]에 저장해주었고,

map[nx][ny]의 값이 1인 경우에는 (벽을 부숴야 하는 경우)

destroy[x][y] + 1의 값과 destroy[nx][ny]을 비교하여 더 작은 값을 저장해주었다.

 

모든 탐색을 완료하면, destroy 벡터에는 해당 위치에 도달하기 위해 파괴한 벽의 최솟값이 저장되게 된다.

즉, destroy[N-1][M-1]이 구하고자 하는 답이 된다.

 

이 문제의 유형은 다익스트라 알고리즘이었다.

그래서 단순 BFS + DP 방식보다 우선순위 큐를 사용해서 파괴한 벽의 수가 적은 것부터 탐색을 했다면,

더 빠르게 답을 찾을 수 있었을 것이다.

 

---

풀이 코드 - C++

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

struct pos {
	int x;
	int y;
};

int main() {
	int map[100][100];
	int destroy[100][100];
	int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
	int N, M;
	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		string a;
		cin >> a;
		for (int j = 0; j < M; j++) {
			map[i][j] = a[j] - '0';
			destroy[i][j] = 987654321;
		}
	};

	queue<pos> q;
	int x, y, nx, ny;
	destroy[0][0] = 0;
	q.push({ 0,0 });
	while (!q.empty()) {
		x = q.front().x, y = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			nx = x + dir[i][0];
			ny = y + dir[i][1];
			if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
			if (map[nx][ny] == 0) {
				if (destroy[nx][ny] > destroy[x][y]) {
					destroy[nx][ny] = destroy[x][y];
					q.push({ nx,ny });
				}
			}
			else {
				if (destroy[nx][ny] > destroy[x][y] + 1) {
					destroy[nx][ny] = destroy[x][y] + 1;
					q.push({ nx,ny });
				}
			}
		}
	}
	cout << destroy[N - 1][M - 1];
}

실행 결과

실행 결과 : 통과 (0ms)