[BOJ] 2665 : 미로만들기 - travelbeeee

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

---

[ 알고리즘풀이 ]

1. BFS 탐색을 진행한다.

2. Visit 을 체크하는 배열을 dp 배열로 선언한다.

dp[x][y] : (0, 0)에서 (x, y)지점까지 가는데 거쳐야하는 '검은방'의 최소 횟수. 로 정의하면

내가 다음에 갈 지점이 '검은방' 이라면 현재 지점의 값 + 1 보다 크다면 가고,  '흰방' 이라면 현재 지점의 값 보다 크다면 간다.

#include<iostream>
#include<queue>

using namespace std;

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

	int n, dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 }, dp[50][50] = {};
	char map[50][51] = {};

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> map[i];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			dp[i][j] = 99999999;

	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));
	dp[0][0] = 0;

	while (!q.empty()) {
		pair<int, int> s = q.front();
		q.pop();

		int curX = s.first, curY = s.second;
		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i], nextY = curY + dy[i];
			if (0 <= nextX && nextX < n && 0 <= nextY && nextY < n) {
				if (dp[curX][curY] + 1 < dp[nextX][nextY] && map[nextX][nextY] == '0') {
					dp[nextX][nextY] = dp[curX][curY] + 1;
					q.push(make_pair(nextX, nextY));
				}
				else if(dp[curX][curY] < dp[nextX][nextY] && map[nextX][nextY] == '1'){
					dp[nextX][nextY] = dp[curX][curY];
					q.push(make_pair(nextX, nextY));
				}
			}
		}
	}
	cout << dp[n - 1][n - 1];
	return 0;
}

---