백준 - 경사로 (14890) [C++]

이 문제는 구현 문제이다. 

 

각 2N개의 길이 경사로를 설치하여 갈 수 있는 길인지를 체크하는 문제이다. N이 100으로 아주 작기 때문에 요구사항만 구현하면 문제가 풀린다.

 

현재와 다음 블럭을 비교했을 때 같은지, 더 높은지, 더 낮은지에 대한 분기문을 작성하여 문제를 해결했다.

다만 주의할 점은 경사로를 설치할 수 있는 높이 차는 최대 1이기 때문에 이를 체크해주지 않으면 오답이 나온다.

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

#define MAX 100

int N, L;
int matrix[MAX][MAX];

int absolute(int num) {
	if (num < 0) {
		return -num;
	}
	
	return num;
}

bool rowCheck(int y) {
	vector<bool> applied(N, false);
	
	for (int x = 0; x < N; x++) {
		if (x == N - 1) {
			continue;
		}

		int present = matrix[y][x];
		int next = matrix[y][x + 1];

		if (absolute(present - next) >= 2) {
			return false;
		}

		if (present == next) {
			continue;
		
		} else if (present < next) {
			int startX = x;
			int endX = x - L + 1;
			if (endX < 0) {
				return false;
			}

			for (int i = startX; i >= endX; i--) {
				if (applied[i]) {
					return false;
				}

				if (present != matrix[y][i]) {
					return false;
				}

				applied[i] = true;
			}
		
		} else {	// present > next
			int startX = x + 1;
			int endX = x + L;
			
			if (endX >= N) {
				return false;
			}

			for (int i = startX; i <= endX; i++) {
				if (applied[i]) {
					return false;
				}

				if (next != matrix[y][i]) {
					return false;
				}

				applied[i] = true;
			}
		}
	}

	return true;
}

bool columnCheck(int x) {
	vector<bool> applied(N, false);

	for (int y = 0; y < N; y++) {
		if (y == N - 1) {
			continue;
		}

		int present = matrix[y][x];
		int next = matrix[y + 1][x];

		if (absolute(present - next) >= 2) {
			return false;
		}

		if (present == next) {
			continue;

		} else if (present < next) {
			int startY = y;
			int endY = y - L + 1;
			if (endY < 0) {
				return false;
			}

			for (int i = startY; i >= endY; i--) {
				if (applied[i]) {
					return false;
				}

				if (present != matrix[i][x]) {
					return false;
				}

				applied[i] = true;
			}

		} else {	// present > next
			int startY = y + 1;
			int endY = y + L;

			if (endY >= N) {
				return false;
			}

			for (int i = startY; i <= endY; i++) {
				if (applied[i]) {
					return false;
				}

				if (next != matrix[i][x]) {
					return false;
				}

				applied[i] = true;
			}
		}
	}

	return true;
}

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

	cin >> N >> L;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> matrix[y][x];
		}
	}

	int answer = 0;

	// row check
	for (int y = 0; y < N; y++) {
		if (rowCheck(y)) {
			answer++;
		}
	}

	// column check
	for (int x = 0; x < N; x++) {
		if (columnCheck(x)) {
			answer++;
		}
	}

	cout << answer << '\n';

	return 0;
}