백준 16932번 모양 만들기

https://www.acmicpc.net/problem/16932

16932번: 모양 만들기

 

 

 

 

 

<접근방법>

0을 하나하나 선택해서 1로 바꾸로 bfs를 돌린다면 매우 비효율적일 것 입니다.

처음에는 bfs를 돌리면서 1로 바꾸는 능력 사용여부를 확인해준다면 될 것이라고 생각했습니다.

실패했습니다.

 

그래서 모든 0에 대해 1로 바꿔보고 바꾸면서 연결되는 덩어리들의 가중치의 합을 구하는 방법으로 문제를 풀었습니다.

미리 덩어리에 번호를 붙이고 가중치를 저장하였습니다.

 

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

struct point {
	int y, x;
};

int n, m, map[1000][1000], res, num;
bool visit[1000][1000];
int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

queue<point> q;
vector<point> zero;
vector<int> w;

void labeling(int y, int x) {
	int tsum = 0;
	q.push({y, x});
	visit[y][x] = true;
	map[y][x] = num;

	while (!q.empty()) {
		tsum++;
		point t = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ty = t.y + dy[i];
			int tx = t.x + dx[i];

			if (ty < 0 || ty >= n || tx < 0 || tx >= m || visit[ty][tx]) continue;
			
			if (map[ty][tx] == 1) {
				q.push({ty, tx});
				visit[ty][tx] = true;
				map[ty][tx] = num;
				//cout << num << '\n';
			}
		}
	}
	w.push_back(tsum);
}

void simul() {
	for (int z = 0; z < zero.size(); z++) {
		int tsum = 0;
		vector<int> v;
		for (int i = 0; i < 4; i++) {
			int ty = zero[z].y + dy[i];
			int tx = zero[z].x + dx[i];

			if (ty < 0 || ty >= n || tx < 0 || tx >= m) continue;

			if (map[ty][tx] != 0) {
				v.push_back(map[ty][tx]);
			}
		}
		if (!v.empty()) {
			sort(v.begin(), v.end());

			tsum += w[v[0]];
			for (int i = 1; i < v.size(); i++) {
				if (v[i] == v[i - 1]) continue;
				tsum += w[v[i]];
			}
		}
		res = max(res, tsum);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0) zero.push_back({i, j});
		}
	}

	num = 1;
	w.push_back(0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 1 && !visit[i][j]) {
				labeling(i, j);
				num++;
			}
		}
	}

	simul();

	cout << res + 1 << '\n';
	return 0;
}