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

오늘은 백준2665번 미로만들기 문제를 풀어보도록 하자. 모든 노드 값을 987654321으로 설정해주었다.(값에 접근할 수 있도록)

그 후 흰 방이 나타나면 visit 값을 비교 후 들어가고, 검은 방이 나타나면 현재 노드 + 1 한 값이 다음 노드의 값보다 작으면 들어가고

queue에 값을 넣어주었다.

문제는 다음과 같다.

                               [접근법]

  1. 일반적인 BFS에서 visit을 값으로 바꿔서 풀어준 것과 같다.
  
  2. 다만 visit값을 boolean이 아닌 987654321의 값을 줌으로써 값에 따라 접근하게 만들어주었다.

                                     [코드]
#include <iostream>
#include <queue>
#include <string>
using namespace std;

int map[50][50];
int visit[50][50];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int N;

struct pos {
	int y;
	int x;
};
queue<pos>Q;

bool Inbound(int y, int x) {
	return y >= 0 && y < N && x >= 0 && x < N;
}

void bfs() {
	Q.push({ 0,0 });
	visit[0][0] = 0;

	while (!Q.empty()) {
		int y = Q.front().y;
		int x = Q.front().x;
		
		Q.pop();

		for (int i = 0; i < 4; i++) {
			int my = y + dir[i][0];
			int mx = x + dir[i][1];

			if (Inbound(my, mx)) {
				if (map[my][mx] == 1) {
					if (visit[my][mx] > visit[y][x]) {//흰방 & 다음 노드 값이 더 크면
						visit[my][mx] = visit[y][x];
						Q.push({ my,mx });
					}
				}
				else {
					if (visit[my][mx] > visit[y][x] + 1) {//검은방 & 다음 노드 값이 현 노드 + 1 보다 크면
						visit[my][mx] = visit[y][x] + 1;
						Q.push({ my,mx });
					}
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visit[i][j] = 987654321;
		}
	}
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < s.length(); j++) {
			map[i][j] = s[j] - '0';
		}
	}
	bfs();
	cout << visit[N - 1][N - 1];
}