https://www.acmicpc.net/problem/16946
16946번: 벽 부수고 이동하기 4
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이
www.acmicpc.net
값이 1인 칸을 0으로 변경했을 때 해당 칸에서 이동할 수 있는 칸의 수를 출력하는 문제입니다.
맵의 크기가 1000 * 1000이고, 모든 1의 칸을 대상으로 탐색하기에는 무조건 시간초과라는 생각이 들었고,
생각해낸 방법은 값이 0인 인접한 칸들에 넘버링을 부여한 후 넘버링의 크기를 더하는 방식입니다.
이것은 bfs를 통해 할 수 있습니다.
방문했던 모든 칸에 대해 넘버링과 카운팅을 합니다.
모든 인접한 칸들의 방문을 마쳤다면 해당 넘버링에 카운팅했던 수를 넣습니다.
그러면 남은 일은 값이 1인 칸에 대해 4방향 탐색하여 인접한 넘버링의 카운트를 모두 더하는 일입니다.
[boj 16932 모양만들기(링크)]에서 하나의 칸을 변경하여 만들 수 있는 모양의 최대 크기를 구한 적이 있습니다.
이 방식과 동일하게 접근하고, 중복된 칸을 예외처리 하기 위해 set을 사용합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#define MAX 1001
#define MOD 10
using namespace std;
typedef pair<int, int> pi;
char list[MAX][MAX];
bool visit[MAX][MAX];
int num[MAX][MAX], ans[MAX][MAX];
int numSize[MAX * MAX];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M;
void func() {
set<int> s;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (list[i][j] == '0') continue;
int sum = 0;
for (int d = 0; d < 4; d++) {
int nx = i + direct[d][0];
int ny = j + direct[d][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (list[nx][ny] != '0') continue;
if (s.find(num[nx][ny]) != s.end()) continue;
sum += numSize[num[nx][ny]];
s.insert(num[nx][ny]);
}
ans[i][j] = (sum + 1) % MOD;
s.clear();
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cout << ans[i][j];
}
cout << '\n';
}
}
void bfs(int sx, int sy, int n) {
queue<pi> q;
q.push({ sx,sy });
visit[sx][sy] = true;
int cnt = 0;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
cnt++;
num[x][y] = n;
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (visit[nx][ny] || list[nx][ny] == '1') continue;
q.push({ nx,ny });
visit[nx][ny] = true;
}
}
numSize[n] = cnt;
}
void init() {
int n = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (visit[i][j] || list[i][j] == '1') continue;
bfs(i, j, n++);
}
}
}
void input() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> list[i];
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
init();
func();
return 0;
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 14466 소가 길을 건너간 이유 6 (1) | 2022.10.13 |
|---|---|
| boj 18112 이진수 게임 (2) | 2022.09.16 |
| boj 5547 일루미네이션 (0) | 2022.05.15 |
| boj 16932 모양 만들기 (0) | 2022.05.14 |
| boj 17244 아맞다우산 (0) | 2021.11.25 |