[백준 1261] 알고스팟

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
int R, C;
char board[100 + 2][100 + 2];

struct _st
{
	int x, y;
	int k;
};

struct COMP
{
	bool operator()(const _st &a, const _st &b)
	{
		return a.k > b.k;
	}
};

std::priority_queue<_st, std::vector<_st>, COMP> PQ;
int chk[100 + 2][100 + 2];

void input()
{
	scanf("%d %d", &C, &R);
	for (int r = 0; r < R; r++) {
		scanf("%s", &board[r]);
	}
}

int BFS()
{
	// dir
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	// init
	PQ = {};
	std::fill(&chk[0][0], &chk[0][0] + sizeof(chk) / sizeof(int), 0x7fffffff);

	PQ.push({ 0, 0 , 0});
	chk[0][0] = 0;

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		if (data.x == R - 1 && data.y == C - 1) return chk[R - 1][C - 1];

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (chk[nx][ny] <= data.k) continue;

			if (board[nx][ny] == '1') {
				if (chk[nx][ny] <= data.k + 1) continue;
				PQ.push({ nx, ny, data.k +1 });
				chk[nx][ny] = data.k + 1;
			}
			else {
				PQ.push({ nx, ny, data.k });
				chk[nx][ny] = data.k;
			}
		}
	}

}



int main()
{
	input();
	int ans = BFS();
	printf("%d\n", ans);
	return 0;
}

"비용"의 관점에서 BFS를 돌려보자.

해당 칸 까지 가는데 벽을 몇 개 부수면서 갔는지가 비용이 될 것이다. 

이를 위해 체크배열을 처음에 아주 큰 수로 초기화해준다. 

만약 가려는 칸에 기록된 비용이 현재 비용보다 작거나 같으면 굳이 가지 않는다. 

만약 가려는 칸에 기록되 비용이 현재 비용보다 크면 벽일때 / 빈칸일때로 나누어 PQ에 push한다. 

우선순위 큐를 사용하였고, 비용이 적은 것을 우선으로 pop해주고 있기 때문에, (R -1, C- 1) 을 가장 처음 만족하는 PQ의 원소가 가장 작은 비용으로 해당 칸에 도달하는 방법이다. 

따라서 바로 return 해줄 수 있다. 

---

무지성 set을 써서 푼 풀이.. 

방문배열 visited[100 +2][100 +2][10000] 가 만들어 지지 않아서, 벽을 1개 부수었을 때 ~ 최대 9998개 부수었을 때 방문할 수 있는 좌표를 S라는 set에 저장해주었다. 

#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
int R, C;
char board[100 + 2][100 + 2];

struct _st
{
	int x, y;
	int k;
};

struct COMP
{
	bool operator()(const _st &a, const _st &b) {
		return a.k > b.k;
	}
};

std::priority_queue<_st, std::vector<_st>, COMP> Q;
std::set<std::pair<int, int>> S[10000];

void input()
{
	scanf("%d %d", &C, &R);
	for (int r = 0; r < R; r++) {
		scanf("%s", &board[r]);
	}
}

int BFS()
{
	// dir
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	// init
	Q.push({ 0, 0 });
	S[0].insert({ 0, 0 });

	while (!Q.empty()) {
		_st data = Q.top();
		Q.pop();

		if (data.x == R - 1 && data.y == C - 1) return data.k;

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (S[data.k].find({ nx, ny }) != S[data.k].end()) continue;

			// 벽
			if (board[nx][ny] == '1') { 
				if (S[data.k + 1].find({ nx, ny }) != S[data.k + 1].end()) continue;
				Q.push({ nx, ny, data.k + 1 });
				S[data.k + 1].insert({ nx ,ny });
			}
			else if (board[nx][ny] == '0') {
				Q.push({ nx ,ny, data.k });
				S[data.k].insert({ nx ,ny });
			}
		}
	}
	return -1;
}

int main()
{
	input();
	int ans = BFS();
	printf("%d\n", ans);
	return 0;
}