백준 [1261] "알고스팟"

기존 BFS와 다른 점이 있는 문제였다.

1. 행, 열 입력받는 것이 반대
2. visit 배열 사용 x

이 문제는 기본적으로 행, 열 입력을 다른 그래프 문제와 반대로 받아 이를 눈치 채지 못해 나중에 수정하느라 시간을 조금 소비했다. 두번째는 그래프 문제는 기본적으로 무한 반복을 하지 않기 위해 visit 배열로 방문을 확인하는데 이건 한번 방문한 map은 다시 방문 하지 못하는 것으로 이 문제와 같이 특정 최소 수를 찾는데는 문제가 있다.

만약 최악의 경우의 수를 갖고 있는 queue가 특정 map을 방문해 그곳의 visit을 true로 바꾼다면 다음 최적의 수 값이 map을 방문할 수 없기 때문이다. 그렇기 때문에 이런 문제를 해결하기 위해서는 시간 여유를 주더라도 다른 방법으로 visit을 구현해야 한다. 현재 조건 값이 [nx][ny]에 위치한 조건의 값보다 우월한지를 확인하는 방식으로 구현했다.

실제로 기존 오류가 나던 코드에서 visit 부분만 삭제하니 바로 정답 처리되었다.

#include <iostream>
#include <queue>

using namespace std;

int n, m;
char miro[101][101];
int dp[101][101];
bool visit[101][101] = { false };

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


void solve() {
	queue<pair<int, int>> q;

	q.push({0,0});
	dp[0][0] = 0;

	while (!q.empty()) {

		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for (int i = 0; i < 4; i++) {

			int nx = x + dx[i];
			int ny = y + dy[i];

			//m이 행, n이 열
			if (0 <= nx && nx < m && 0 <= ny && ny < n) {

				if (miro[nx][ny] == '0' && dp[x][y] < dp[nx][ny]) {
					dp[nx][ny] = dp[x][y];
					q.push({ nx,ny });
				}

				else if (miro[nx][ny] == '1' && dp[x][y]+1 < dp[nx][ny]) {
					dp[nx][ny] = dp[x][y] + 1;
					q.push({ nx,ny });
				}
			}
		}

	}
	cout << dp[m-1][n-1];
}

void input() {

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		string a;
		cin >> a;
		for (int j = 0; j < a.size(); j++) {
			miro[i][j] = a[j];
			dp[i][j] = INT_MAX;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input();
	solve();

	return 0;
}