[백준 C++] 2115 갤러리

문제

갤러리의 지도는 M*N의 정사각형 격자로 표현될 수 있다. 어떤 정사각형들은 벽으로 구성되어 있고, 다른 정사각형들은 빈 공간으로 구성되어 있다. 벽을 회색, 빈 공간을 흰색으로 표현하면 다음 그림과 같다.

갤러리에 그림을 걸려고 한다. 그림의 길이는 정사각형의 변의 길이의 두 배이다. 반드시 빈 공간과 인접해 있는 벽에만 그림을 걸 수 있으며, 그림들은 서로 겹칠 수 없다. 갤러리의 맵이 주어졌을 때, 최대로 걸 수 있는 그림의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 갤러리의 세로 길이 M과 가로 길이 N이 주어진다. (1 ≤ M, N ≤ 1,000) 다음 M개의 줄에는 각각 N개의 문자가 주어진다. 문자는 'X' 또는 '.'이며 'X'는 벽을, '.'는 빈 공간을 나타낸다.

입력되는 모든 데이터에서 적어도 첫 줄과 마지막 줄, 첫 열과 마지막 열은 모두 벽이다.

출력

최대 그림 개수를 출력한다.

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

풀이

그래프탐색도 필요없다.
모든 빈공간에서, 상하좌우가 벽으로 구성되있는경우에,
연속된 2개이상만을 찾으면된다.

오른쪽으로 빈공간을 찾아 탐색, 이때 빈공간발견시 바로 위에 벽이 있는경우 갯수 cnt를 증가,
빈공간이아니거나 벽이없는경우(바로 위에 또 빈공간인경우) 에는 cnt를 2로 나눈값을 저장해주었다.
다른 3가지 방향도 마찬가지

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
int m, n;
bool** gallery;

void init() {
	scanf("%d%d", &m, &n);
	gallery = new bool* [m];
	for (int i = 0; i < m; i++) {
		gallery[i] = new bool[n];
		char _;
		scanf("%c", &_);
		for (int j = 0; j < n; j++) {
			scanf("%c", &_);
			if (_ == 'X')
				gallery[i][j] = false;
			else if (_ == '.')
				gallery[i][j] = true;
		}
	}
}

void func() {
	int res = 0;

	for (int k = 1; k < m - 1; k++) { // → 방향 윗벽 탐색
		int cnt = 0;
		for (int l = 1; l < n - 1; l++) {
			if (gallery[k][l] && !gallery[k - 1][l])
				cnt++;
			else{
				res += cnt / 2;
				cnt = 0;
			}
		}
		res += cnt / 2;
	}
	for (int k = 1; k < m - 1; k++) { // → 방향 아랫벽 탐색
		int cnt = 0;
		for (int l = 1; l < n - 1; l++) {
			if (gallery[k][l] && !gallery[k + 1][l])
				cnt++;
			else{
				res += cnt / 2;
				cnt = 0;
			}
		}
		res += cnt / 2;
	}
	for (int k = 1; k < n - 1; k++) { // ↓ 방향 왼벽탐색
		int cnt = 0;
		for (int l = 1; l < m - 1; l++) {
			if (gallery[l][k] && !gallery[l][k - 1])
				cnt++;
			else{
				res += cnt / 2;
				cnt = 0;
			}
		}
		res += cnt / 2;
	}
	for (int k = 1; k < n - 1; k++) { // ↓ 방향 오른벽탐색
		int cnt = 0;
		for (int l = 1; l < m - 1; l++) {
			if (gallery[l][k] && !gallery[l][k + 1])
				cnt++;
			else{
				res += cnt / 2;
				cnt = 0;
			}
		}
		res += cnt / 2;
	}

	printf("%d", res);
}


int main(void) {
	init();
	func();

	return 0;
}