백준 1261번 문제 알고스팟 풀이

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

백준저지 1261번 문제인 알고스팟 풀이입니다.

벽을 몇개를 부숴야 하는지를 알아야 하므로, 벽을 부술 때 만 값을 1 증가시키는 식으로 BFS를 합니다.

다만, 벽을 부수지 않는 경우들을 우선적으로 처리하도록 하기 위해서 큐 대신 우선순위 큐(벽 부순 값이 낮은 것 부터 리턴하도록 Min Heap 사용)를 활용

합니다.

 

#include <iostream>
#include <queue>
#include <string>
using namespace std;

string map[101];
struct State {
	int val, x, y;
	bool operator<(const struct State& rhs) const {
		return val > rhs.val;
	}
};
const int dx[] = { +1, +0, +0, -1 };
const int dy[] = { +0, +1, -1, +0 };
bool v[101][101];
int main() {
#ifdef WIN32
	freopen("in.txt", "r", stdin);
#endif
	int M, N;
	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		cin >> map[i];
	}
	priority_queue<State> pq;
	pq.push({ 0, 0, 0 });

	while (pq.size()) {
		auto cur = pq.top();
		pq.pop();
		if (cur.x == N - 1 && cur.y == M - 1) {
			cout << cur.val << endl;
			return 0;
		}
		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
			if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
			if (v[nx][ny]) continue;
			v[nx][ny] = 1;
			pq.push({ cur.val + (map[nx][ny] == '1' ? 1 : 0 ), nx, ny });
		}
	}
}

두번째 풀이법으로는 비슷한 방식이나 구현이 조금 다릅니다.

벽을 부수지 않고 이동할 수 있는 공간을 하나의 큰 정점으로 그룹핑합니다. 

N, M좌표에서 먼저 큰 정점으로 만들어서 2로 마킹하고, 정점간 이동으로 BFS 탐색을 하면서 2로 마킹된 정점을 찾습니다.

정점간 이동은 벽을 하나 부수는 것과 같이 동작하므로 최소 부수는 벽의개수를 알 수 있게 됩니다.

 

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <cstring>
using namespace std;

string map[101];
struct State {
	int val, x, y;
};
struct Pos {
	int x, y;
};
const int dx[] = { +1, +0, +0, -1 };
const int dy[] = { +0, +1, -1, +0 };
bool v[101][101];
int M, N;
vector<Pos> edges[101][101];
void bfs(int sx, int sy) {
	memset(v, 0, sizeof(v));
	queue<Pos> q;
	q.push({ sx, sy });
	v[sx][sy] = 1;
	while (q.size()) {
		auto c = q.front(); q.pop();
		if ((map[c.x][c.y] == '1' || map[c.x][c.y] == '2') && !(c.x == sx && c.y == sy)) {
			edges[sx][sy].push_back({ c.x, c.y });
		}
		else {
			for (int i = 0; i < 4; i++) {
				int nx = c.x + dx[i];
				int ny = c.y + dy[i];
				if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
				if (v[nx][ny]) continue;
				v[nx][ny] = 1;
				q.push({ nx, ny });
			}
		}
	}
}
void dfs(int x, int y) {
	v[x][y] = 1;
	map[x][y] = '2';
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
		if (v[nx][ny]) continue;
		if (map[nx][ny] == '1') {
			continue;
		}
		map[nx][ny] = '2';
		dfs(nx, ny);
	}
}
int main() {
#ifdef WIN32
	freopen("in.txt", "r", stdin);
#endif

	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		cin >> map[i];
	}

	dfs(N - 1, M - 1);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			bfs(i, j);
		}
	}
	memset(v, 0, sizeof(v));
	
	queue<State> q;
	q.push({ 0, 0, 0 });
	v[0][0] = 1;
	if (map[0][0] == '2') {
		cout << 0 << endl;
		return 0;
	}

	while (q.size()) {
		auto c = q.front(); q.pop();
		for (auto n : edges[c.x][c.y]) {
			if (v[n.x][n.y]) continue;
			v[n.x][n.y] = 1;
			if (map[n.x][n.y] == '2') {
				cout << c.val << endl;
				return 0;
			}
			q.push({ c.val + 1, n.x, n.y });
		}
	}
	
}