BOJ_14890 : 경사로

문제

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.

오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.

다음과 같은 N=6인 경우 지도를 살펴보자.

(이하생략)

입력

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int n, l;
int arr[101][101];

bool go(vector<int> a) {
	// 한줄검사
	vector<bool> check(n, false);
	for (int y = 0; y < n-1; y++) {
		int diff = a[y] - a[y + 1];
		if (diff == 0) continue;
		else if (diff == 1 ) {
			// i > i + 1
			if (y + l >= n) return false;
			for (int i = 1; i < l; i++) {
				// 다음 길의 높이가 같다면
				if (a[y + i] == a[y + i + 1]) {

					continue;
				}
				// 높이가 다르다면
				else {
					return false;
				}
			}
			// 경사로 건설
			for (int i = 1; i <= l; i++) {
				check[y + i] = true;
			}
			continue;

		}
		else if (diff == -1) {
			// i < i + 1
			if (y - l + 1 < 0 || check[y]) return false;
			for (int i = 1; i < l; i++) {

				// 다음 길의 높이가 같다면
				if (a[y] == a[y - i] && !check[y-i]) {
					continue;
				}
				// 높이가 다르다면
				else {
					return false;
				}
			}
			// 경사로 건설
			for (int i = 0; i < l; i++) {
				check[y - i] = true;
			}
			continue;
		}
		else {
			return false;
		}
	}
	// 끝까지 가능한 경우
	return true;
}


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

	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	int ans = 0;

	// 행 검사
	for (int i = 0; i < n; i++) {
		vector<int> a(n);
		for (int j = 0; j < n; j++) {
			a[j] = arr[i][j];
		}
		if (go(a)) ans++;
	}
	// 열 검사
	for (int i = 0; i < n; i++) {
		vector<int> a(n);
		for (int j = 0; j < n; j++) {
			a[j] = arr[j][i];
		}
		if (go(a)) ans++;
	}

	cout << ans << '\n';
	return 0;
}