문제는 기존 문제 변형한 것이지만,
이 문제의 알고리즘은 BFS, DFS이다.
BFS는 Breadth기준으로 해서 찾는 것을 말한다.
방향의 기준으로해서 모든 경우를 찾아야 한다.
즉, 문제에서는 0은 패스하고, 1인 경우는 벽을 부수고, 이동할 수 있는 칸의 개수를 10으로 나누면 된다는 것이다.
코드는 많이 기므로, 참고용으로만 쓰길 바란다.
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int N, M;
int map[1000][1000];
int visited[1000][1000];
int group[1000][1000];
int groupSize[1000000];
int groupNum = 1;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
queue<pair<int, int>> q;
void bfs(int y, int x) {
int cnt = 1;
q.push({y, x});
visited[y][x] = 1;
group[y][x] = groupNum;
while (!q.empty()) {
int curY = q.front().first;
int curX = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nextY = curY + dir[i][0];
int nextX = curX + dir[i][1];
if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M) continue;
if (visited[nextY][nextX] || map[nextY][nextX]) continue;
visited[nextY][nextX] = 1;
group[nextY][nextX] = groupNum;
q.push({nextY, nextX});
cnt++;
}
}
groupSize[groupNum] = cnt;
groupNum++;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
char c;
cin >> c;
map[i][j] = c - '0';
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (!visited[i][j] && !map[i][j]) {
bfs(i, j);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j]) {
int sum = 1;
vector<int> v;
for (int k = 0; k < 4; k++) {
int nextY = i + dir[k][0];
int nextX = j + dir[k][1];
if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M) continue;
if (map[nextY][nextX]) continue;
if (find(v.begin(), v.end(), group[nextY][nextX]) == v.end()) {
v.push_back(group[nextY][nextX]);
sum += groupSize[group[nextY][nextX]];
}
}
cout << sum % 10;
} else {
cout << 0;
}
}
cout << '\n';
}
return 0;
}
너무 기네...
ㅋㅋㅋㅋㅋㅋㅋㅋ
'백준 온라인 저지 싹쓸이' 카테고리의 다른 글
[BOJ16724] 피리 부는 사나이 (1) | 2022.09.25 |
---|---|
[BOJ4386] 별자리 만들기 (1) | 2022.09.24 |
[BOJ2887] 행성 터널 (0) | 2022.09.24 |
[BOJ 11257] IT 시험 (0) | 2022.09.23 |
[BOJ2473] 세 용액 (1) | 2022.09.22 |