취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 32715번 문제인 십자 찾기이다.
문제는 아래 링크를 확인하자.

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

각 칸마다 해당 칸에서부터 상하좌우로 연속으로 몇 칸씩 모눈이 색칠되어있는지를 안다면 문제를 쉽게 해결할 수 있을 것이다. 그러나 각 칸에서 직접 연속된 칸을 방향별로 세는 것은 좋은 전략은 아닌데, 모든 모눈이 색칠되어있는 등 극단적인 경우 실행시간이 오래 걸릴 수 있기 때문이다.

prefix sum을 이용해 방향별로 몇 칸이 연속 색칠되어있는지 미리 전처리를 해 실행시간을 줄이자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int R, C, K, ans;
short A[2502][2502][4];

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

	cin >> R >> C >> K;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			cin >> A[r][c][0];
			A[r][c][1] = A[r][c][2] = A[r][c][3] = A[r][c][0];
		}
	}
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			if (A[r][c][0]) A[r][c][0] += A[r][c - 1][0];
		}
	}
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			if (A[r][c][1]) A[r][c][1] += A[r - 1][c][1];
		}
	}
	for (int r = R; r > 0; r--) {
		for (int c = C; c > 0; c--) {
			if (A[r][c][2]) A[r][c][2] += A[r][c + 1][2];
		}
	}
	for (int r = R; r > 0; r--) {
		for (int c = C; c > 0; c--) {
			if (A[r][c][3]) A[r][c][3] += A[r + 1][c][3];
			if (A[r][c][0] > K && A[r][c][1] > K && A[r][c][2] > K && A[r][c][3] > K) ans++;
		}
	}

	cout << ans;
}