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

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

14890번: 경사로

구현 문제다.

 

모든 경우의 수를 고려해서 경사로를 놓을 수 있는지 확인하면 된다.

#include <iostream>
using namespace std;

int arr[100][100];
int visit[100][100];

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, l, re = 0;	cin >> n >> l;

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

	// 가로
	for (int i = 0; i < n; i++) {
		// 평지의 개수를 세는 변수, 지나갈 수 있는 칸의 수
		int g = 1, cnt = 0;

		for (int j = 0; j < n - 1; j++) {
			int gap = arr[i][j] - arr[i][j + 1];
			// 경사 높이가 1보다 크면 경사로를 놓을 수 없음
			if (gap > 1 || gap < -1) break;
			
			// 경사가 없다면 평지 수 + 1
			if (gap == 0) g++;

			// 경사 높이가 1이면 (내리막길)
			else if (gap == 1) {
				// 평지 수 초기화 0
				g = 0;

				// 남아 있는 칸이 경사로의 길이보다 작다면 break
				if (n - 1 - j < l) break;

				// 남아 있는 칸들 중 경사로의 길이만큼 평지인지 확인
				int k = j;
				j++;
				for (j; j < k + l; j++)
					if (arr[i][j] != arr[i][j + 1]) break;
				j--;

				if (j + 1 != k + l) break;
				cnt += (l - 1);
			}

			// 경사 높이가 -1이면 (오르막길)
			else if (gap == -1) {
				// g를 사용하기 위해 다른 변수에 저장
				int k = g;
				// g 초기화
				g = 1;

				if (j + 1 < l) break;

				// 평지 수가 경사로의 길이보다 작다면 break
				if (k < l) break;
			}

			cnt++;
		}
		if (cnt == n - 1) re++;
	}

	// 세로
	for (int i = 0; i < n; i++) {
		// 평지의 개수를 세는 변수, 지나갈 수 있는 칸의 수
		int g = 1, cnt = 0;

		for (int j = 0; j < n - 1; j++) {
			int gap = arr[j][i] - arr[j + 1][i];
			// 경사 높이가 1보다 크면 경사로를 놓을 수 없음
			if (gap > 1 || gap < -1) break;

			// 경사가 없다면 평지 수 + 1
			if (gap == 0) g++;

			// 경사 높이가 1이면 (내리막길)
			else if (gap == 1) {
				// 평지 수 초기화 0
				g = 0;

				// 남아 있는 칸이 경사로의 길이보다 작다면 break
				if (n - 1 - j < l) break;

				// 남아 있는 칸들 중 경사로의 길이만큼 평지인지 확인
				int k = j;
				j++;
				for (j; j < k + l; j++)
					if (arr[j][i] != arr[j + 1][i]) break;
				j--;
				if (j + 1 != k + l) break;
				cnt += (l - 1);
			}

			// 경사 높이가 -1이면 (오르막길)
			else if (gap == -1) {
				// g를 사용하기 위해 다른 변수에 저장
				int k = g;
				// g 초기화
				g = 1;
				if (j + 1 < l) break;

				// 평지 수가 경사로의 길이보다 작다면 break
				if (k < l) break;
			}

			cnt++;
		}
		if (cnt == n - 1) re++;
	}

	cout << re;
}