https://www.acmicpc.net/problem/16932
16932번: 모양 만들기
N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의
www.acmicpc.net
정말 오랜만에 알고리즘 포스팅입니다.
이 문제는 배열의 값이 0인 한 칸을 1로 변경하여 만들 수 있는 모양의 최대 크기를 구하는 문제입니다.
이 문제에서 모양이란 배열 내에서 1로 이루어진 연결 요소입니다.
저는 bfs를 통해 1로 이루어진 모양들을 넘버링하여 해당 넘버링의 크기를 vector에 넣어주었고,
브루트포스를 통해 값이 0인 칸들의 인접한 칸들의 크기 합을 구해 max를 구하였습니다.
이 때, 인접한 칸에서 같은 넘버링이 나올 수 있으므로 중복체크를 위해 set을 사용하였습니다.
넘버링했다는 것은
0 1 1
0 0 1
0 1 0이렇게 되어있는 배열을
0 1 1
0 0 1
0 2 0이렇게 모양별로 구분할 수 있도록 변경하였습니다.
이 상태에서 브루트포스로 모양들을 연결해주는 것입니다.
여기서 인접한 칸에서 같은 넘버링이 나오는 경우는 좌표 (1, 1)을 보시면 이해하실 수 있습니다.
0 1 1
0 0 1
0 2 0
(1, 1)을 1로 변경한다고 했을 때 위(0, 1)와 오른쪽(1, 2)은 같은 넘버링을 가진 모양입니다.
이미 같은 모양에 속하므로 이를 중복으로 더해서는 안됩니다.
따라서 중복체크를 위해 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
|
#include <iostream>
#include <queue>
#include <vector>
#include <set>
#define MAX 1001
using namespace std;
typedef pair<int, int> pi;
int list[MAX][MAX];
bool visit[MAX][MAX];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
vector<int> sizeList;
int N, M;
void bfs(int sx, int sy, int num) {
int ret = 0;
queue<pi> q;
q.push({ sx,sy });
visit[sx][sy] = true;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
ret++;
list[x][y] = num;
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 (!list[nx][ny] || visit[nx][ny]) continue;
q.push({ nx,ny });
visit[nx][ny] = true;
}
}
sizeList.push_back(ret);
}
void func() {
sizeList.push_back(0);
int num = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (!list[i][j] || visit[i][j]) continue;
bfs(i, j, num++);
}
}
int ans = 0;
set<int> s;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (list[i][j]) continue;
int ret = 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]) continue;
if (s.find(list[nx][ny]) != s.end()) continue;
s.insert(list[nx][ny]);
ret += sizeList[list[nx][ny]];
}
ans = max(ans, ret + 1);
s.clear();
}
}
cout << ans << '\n';
}
void input() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> list[i][j];
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 16946 벽 부수고 이동하기 4 (0) | 2022.05.22 |
|---|---|
| boj 5547 일루미네이션 (0) | 2022.05.15 |
| boj 17244 아맞다우산 (0) | 2021.11.25 |
| boj 1194 달이 차오른다, 가자. (0) | 2021.04.21 |
| boj 17471 게리맨더링 (0) | 2021.04.16 |