[백준/BOJ] 백준 16932번 : 모양 만들기

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

16932번: 모양 만들기

 

1이 있는 위치를 인접한 칸으로 연결한 것을 하나의 영역으로 다뤄서, 1의 위치마다 어떤 영역에 속하고, 영역마다 영역의 크기를 저장해 놓고, 모든 위치를 확인하며, 해당 위치가 0이면 해당 위치를 1로 만들었을 때 인접한 영역 부분을 고려하여 만들어지는 영역의 크기를 구해서 확인하고, 해당 위치가 1이면 해당 영역의 크기를 확인하는 방법으로 최대 크기를 구해서 문제를 해결했다.

 

코드

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

int n, m;
int board[1005][1005];
int area_number[1005][1005]; //해당 위치의 영역 번호 표시
int area_size[1000005]; //[영역 번호] = 해당 영역의 크기
int area_number_cnt = 0;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

void pre() {
	for (int i = 0; i < 1005; i++) {
		for (int j = 0; j < 1005; j++) {
			board[i][j] = 0;
			area_number[i][j] = 0;
		}
	}

	for (int i = 0; i < 1000005; i++) {
		area_size[i] = 0;
	}
}

//dfs로 인접 영역 번호 매기기
void dfs(pair<int, int> here) {
	area_number[here.first][here.second] = area_number_cnt;
	area_size[area_number_cnt]++;

	for (int dir = 0; dir < 4; dir++) {
		pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);

		//there가 1인데 아직 영역 번호가 매겨져 있지 않을때
		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && board[there.first][there.second] != 0 && area_number[there.first][there.second] == 0) {
			dfs(there);
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	pre();

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int input;
			cin >> input;

			board[i][j] = input;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			//1이 있는 칸인데 영역 번호가 배정되지 않은 칸일때
			//dfs하며 영역 번호를 배정한다
			if (board[i][j] != 0 && area_number[i][j] == 0) {
				area_number_cnt++;
				dfs(make_pair(i, j));
			}
		}
	}

	int result = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {

			//이곳을 1로 가정했을때 인접한 부분을 고려해본다
			if (board[i][j] == 0) {

				set<int> temp_area_number;
				set<int>::iterator it;

				int temp = 0;

				for (int dir = 0; dir < 4; dir++) {
					pair<int, int> there = make_pair(i + dxdy[dir][0], j + dxdy[dir][1]);

					if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && board[there.first][there.second] != 0) {
						temp_area_number.insert(area_number[there.first][there.second]);
					}
				}

				for (it = temp_area_number.begin(); it != temp_area_number.end(); it++) {
					temp += area_size[(*it)];
				}

				temp += 1; //현재 위치까지 더하기

				result = max(result, temp);
			}

			//해당 지역 자체의 크기
			else {
				result = max(result, area_size[area_number[i][j]]);
			}
		}
	}

	cout << result;

	return 0;
}