[BOJ] 16932. 모양 만들기

* dfs를 이용하여 1로 이루어진 그룹을 라벨링한다. (그룹에 몇 개의 1이 있는지 labelCnt[]에 저장한다)

* 현재 좌표의 값이 1이고, 상 하 좌 우 인접한 값이 0인 좌표를 중심으로 탐색을 한다. 

인접한 좌표에 0이 있다면 이 값을 1로 바꾸고 다른 그룹들과 합쳐질 수 있다. -> 이를 가능하게 하려면, 0인 좌표의 인접한 칸에 다른 그룹이 있어야 한다. 

* 만약, 0인 좌표가 다른 그룹과 인접해 있다면 (연합 그룹을 형성하는 1의 개수와 현재 그룹의 개수 +1 )의 최대값이 정답이 된다. 

* 주의해야 할 점은, 0이 같은 그룹으로 이루어진 1들로 둘러싸여져있을 수 있기 때문에 중복으로 더해주는 것을 방지해야 한다. 

(set에 그룹의 라벨을 넣어주어서 중복으로 세지 않도록 하였다. )

1	1	0	0	0
1	1	0	0	0
1	0	1	0	0
0	1	1	0	0
0	0	0	0	0

1	1	0	0	0
1	1	0	0	0
1	0	2	0	0
0	2	2	0	0
0	0	0	0	0

 

 

#include <iostream> #include <vector> #include <cstring> #include <queue> #include <set> using namespace std; //boj 모양 만들기 https://www.acmicpc.net/problem/16932 int n, m; int map[1001][1001]; bool visited[1001][1001]; int labelMap[1001][1001]; int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0}; int labelCnt[1000001]; bool chk[1001][1001]; typedef pair<int, int> pp; int max(const int &a, const int &b) { if (a > b) return a; return b; } bool checkRange(int nx, int ny) { if (nx < 0 || nx >= n || ny < 0 || ny >= m) return false; return true; } void dfs(int x, int y, int label) { visited[x][y] = true; labelMap[x][y] = label; labelCnt[label]++; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (checkRange(nx, ny) && map[nx][ny] && !visited[nx][ny]) { dfs(nx, ny, label); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; } } //수를 하나 변경해서 1이 연결되는 최대 값을 구한다. //두 개로 나눠져있다면 그 두개를 연결하는 좌표를바꾸면 된다. int label = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] && !visited[i][j]) { ++label; dfs(i, j, label); } } } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j]) { for (int d = 0; d < 4; d++) { int nx = i + dx[d]; int ny = j + dy[d]; if (checkRange(nx, ny) && !map[nx][ny] && !chk[nx][ny]) { chk[nx][ny] = true; int res = labelCnt[labelMap[i][j]]; set<int> combine; set<int>::iterator it; for (int k = 0; k < 4; k++) { int nnx = nx + dx[k]; int nny = ny + dy[k]; if (checkRange(nnx, nny) && labelMap[nnx][nny] && labelMap[nnx][nny] != labelMap[i][j]) { combine.insert(labelMap[nnx][nny]); } } for (it = combine.begin(); it != combine.end(); it++) { res += labelCnt[*it]; } ans = max(ans, res + 1); } } } } } cout << ans << '\n'; return 0; }