[C++] 백준 2665번-미로만들기

BOJ 2665-미로만들기

문제

예제 입력

8
11100110
11010010
10011010
11101100
01000111
00110001
11011000
11000111

에제 출력

2

풀이

BFS를 사용하여 풀었다.

1. board의 맵을 저장하고 flag는 방문 시 가장 적은 횟수로 벽을 부셨던 경우다.
2. queue에 좌표(x,y)와 부순 횟수(c)를 담는다.
3. queue를 탐색하고 현재 탐색 노드의 flag값보다 c가 크면 다음으로 넘어간다.
4. 도착지점이면 답을 갱신한다.
5. 주변 4개의 타일을 큐에 삽입한다.

소스코드

#include "bits/stdc++.h"

using namespace std;
#define MAX 10000000

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

int board[51][51];
int flag[51][51];

int answer = MAX;
int n;
bool InMap(int x, int y) {
	if (0 <= x && x < n && 0 <= y && y < n)
		return true;
	return false;
}

void BFS() {
	queue<tuple<int, int, int>> q;
	q.push({ 0,0,0 });

	while (!q.empty()) {
		int x = get<0>(q.front());
		int y = get<1>(q.front());
		int c = get<2>(q.front());

		q.pop();

		if (!InMap(x, y)) {
			continue;
		}

		if (c >= answer)
			continue;

		if (board[y][x] == 0) {
			c += 1;
		}

		if (flag[y][x] <= c) {
			continue;
		}
		
		flag[y][x] = c;

		if (x == n - 1 && y == n - 1) {
			answer = min(answer, c);
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			q.push({ nx,ny,c });
		}
	}

	if (answer == MAX)
		answer = 0;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int y = 0; y < n; y++) {
		string s;
		cin >> s;
		for (int x = 0; x < s.length(); x++) {
			board[y][x] = ((int)s[x] - (int)'0');
			flag[y][x] = MAX;
		}
	}

	BFS();
	cout << answer;
}