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 });
}
}
}