[C++]백준16932번 모양 만들기

오늘은 백준16932번 모양 만들기 문제를 풀어보도록 하자.

인접한 점들을 grouping하여 cnt를 해주고 그 후 0인 지점들의 4방향을 탐색하며 겹치는 grouping number를 제외하며 cnt해주었다.

실행시간이 너무 오래걸려서 후에 다시 고쳐봐야겠다..

문제는 다음과 같다.

                               [접근법]

  1. 우선 map은 3차원을 사용해주었다. map[][][0]은 입력을 받고, map[][][1]은 grouping index를 부여할 것이다.

  2. grouping index를 부여할 때는 dfs를 사용해주었다. bfs로 했으면 좀 더 빨랐을 것 같다.
  
  3. 그 후 find_max함수를 이용하여 map[][][0] == 0 일 때 4방향 탐색을 진행한다. 주의해야 할 점은 grouping index가 겹치면 안되기 때문에 true 처리를 하고 다 끝났으면 false를 해주는 방식으로 했다.

                                     [코드]
#include <iostream>
using namespace std;

int R, C, answer = 0, temp = 0, cnt = 0;
int map[1000][1000][2];
bool visit[1000][1000];
bool check[1000000]; // 그룹 중복 체크
int group[1000000];// 그룹의 섬 갯수
int dir[4][2] = { {-1,0}, {0,1},{1,0},{0,-1} };

bool Inbound(int y, int x) {
	return y >= 0 && x >= 0 && y < R && x < C;
}
void Init_check() {
	for (int i = 0; i <= temp; i++)check[i] = false;
}

void find_max(int y, int x) {
	int temp_cnt = 1;
	for (int i = 0; i < 4; i++) {
		int my = y + dir[i][0];
		int mx = x + dir[i][1];

		if (Inbound(my, mx)) {
			if (!check[map[my][mx][1]] && map[my][mx][0] == 1) {
				check[map[my][mx][1]] = true;
				temp_cnt += group[map[my][mx][1]];
			}
		}
	}
	if (answer < temp_cnt)answer = temp_cnt;
	Init_check();
}

void dfs(int y, int x) {
	visit[y][x] = true;
	map[y][x][1] = temp;
	cnt++;
	for (int i = 0; i < 4; i++) {
		int my = y + dir[i][0];
		int mx = x + dir[i][1];

		if (Inbound(my, mx)) {
			if (!visit[my][mx]) {
				if (map[my][mx][0] == 1 && !visit[my][mx]) {
					dfs(my, mx);
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j][0];
		}
	}
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (map[i][j][0] == 1 && !visit[i][j]) {
				dfs(i, j);
				group[temp] = cnt;
				cnt = 0;
				temp++;
			}
		}
	}
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (map[i][j][0] == 0) {
				find_max(i,j);
			}
		}
	}
	cout << answer;
}