BOJ (C/C++) 2665번: 미로만들기

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

2665번: 미로만들기

---

풀이

이 문제는 가장 빠른 경로를 찾는 것이 아닌 바꾼 벽의 개수가 최소인 경로를 찾는 문제이므로 bfs를 약간 변형해서 풀었다.

 

방문 여부가 아닌 현재 지점에 도달하기까지 바꾼 벽의 개수를 저장했다.따라서 초기값은 문제에서 나올 수 없는 큰 값으로 설정해놓고, 시작지점의 값을 0으로 설정한 후에 탐색을 하며 벽이 바뀌어야 할 경우 값을 증가시키며 bfs를 실행했다.이 때, 탐색하고자 하는 지점에 도달할 때까지 바꾼 벽의 개수가 해당 지점에 저장된 값보다 크다면 탐색할 필요가 없다.

---

코드

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

bool map[50][50];

int Find(int n) {
	int d[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
	int x, y, cnt, nx, ny;
	int changed[50][50];
	queue <pair<pair<int, int>, int>> Q;

	// init
	fill(changed[0], changed[50], 10000);
	Q.push({ { 0,0 }, 0 });
	changed[0][0] = 0;

	
	while (!Q.empty()) {
		// (x,y) : 현재좌표, cnt : (x,y)에 올 때까지 바꾼 벽의 개수
		x = Q.front().first.first, y = Q.front().first.second, cnt = Q.front().second;
		Q.pop();

		for (int i = 0; i < 4; i++) {
			nx = x + d[i][0], ny = y + d[i][1];

			// 탐색하고자 하는 위치에 도달하기 위해 바꾼 벽의 개수가 현재보다 작거나 같다면 탐색할 이유 x
			if (nx < 0 || nx >= n || ny < 0 || ny >= n || changed[nx][ny] <= cnt) continue;

			
			if (map[nx][ny] == 0) {
				changed[nx][ny] = cnt + 1; // 바꾼 횟수 증가
				Q.push({ {nx,ny},cnt + 1 });
			}
			else {
				changed[nx][ny] = cnt;
				Q.push({ {nx,ny},cnt });
			}
		}
	}
	return changed[n - 1][n - 1];
}
int main() {
	int n;
	char s[51];

	// input
	scanf("%d\n", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", s);
		for (int j = 0; j < n; j++) map[i][j] = s[j]-'0';
	}

	printf("%d", Find(n));
	return 0;
}