[백준 2665] 미로만들기 (C++)

문제 링크: https://www.acmicpc.net/problem/2665

2665번: 미로만들기

1. 주의할 점

- 해당 칸에 도착하기 위해 바꾼 방의 최소 개수를 Check 배열에 저장한다

- 새로 방문하는 칸의 Check값을 잘 비교해야 한다

 

 

2. 구현

- BFS를 통해 문제를 해결한다

- Check배열을 전부 3000으로 초기화 한다 (50*50보다 큰 값으로 설정하면 된다)

- 이동하려는 칸이 1인 경우, 이동하려는 칸의 Check값이 CV(현재까지 바꾼 방의 개수)보다 크다면 Check값을 CV로 갱신하고 이동하려는 칸을 큐에 추가한다

- 이동하려는 칸이 0인 경우, 이동하려는 칸의 Check값이 CV(현재까지 바꾼 방의 개수) + 1보다 크다면 Check값을 CV+1로 갱신하고 이동하려는 칸을 큐에 추가한다

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;
struct info {
	int x, y, val;
};
info tmp;
int result = 3000, num, arr[50][50], check[50][50];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

int main() {
	cin >> num;
	string str;
	for (int i = 0; i < num; i++) {
		cin >> str;
		for (int j = 0; j < num; j++) {
			arr[i][j] = str[j] - '0';
			check[i][j] = 3000;
		}
	}
	queue<info> q;
	tmp.x = 0;
	tmp.y = 0;
	tmp.val = 0;
	q.push(tmp);
	check[0][0] = 0;
	while (!q.empty()) {
		int cx = q.front().x;
		int cy = q.front().y;
		int cv = q.front().val;
		q.pop();
		if (cx == num - 1 && cy == num - 1) {
			result = min(result, cv);
			continue;
		}
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx >= 0 && ny >= 0 && nx < num && ny < num) {
				if (arr[ny][nx] == 1 && check[ny][nx] > cv) {
					check[ny][nx] = cv;
					tmp.x = nx;
					tmp.y = ny;
					tmp.val = cv;
					q.push(tmp);
				}
				if (arr[ny][nx] == 0 && check[ny][nx] > cv + 1) {
					check[ny][nx] = cv + 1;
					tmp.x = nx;
					tmp.y = ny;
					tmp.val = cv + 1;
					q.push(tmp);
				}
			}
		}
	}
	cout << result;
	system("pause");
	return 0;
}