백준 14890 경사로

- 단순(하지만 시간이 많이 걸리는) 구현 문제이다. 시간복잡도는 O(n^2)이다.

 

- 각 행과 각 열에 대해 test를 거쳐서, 경사로를 놓아 지나갈 수 있는 길을 몇 개나 만들 수 있는지를 체크하면 된다. 

따라서, check하는 함수를 따로 두고 vector를 넘겨서 체크하도록 하였다. 만약 이렇게 하지 않는다면 4중 for문이 되어 코드의 가독성이 많이 떨어지게 된다.

 

 

- 조건에 따라 분기를 해 준다.

 

 

1. 인접한 두 개의 칸을 비교해서 높이가 다른 경우

  1) 두 칸의 높이 차가 1을 초과하는 경우 -> false

  2) 두 칸의 차이가 1인 경우

    (1) 이전 칸이 다음 칸보다 작은 경우

      => 이전 칸(i-1)에서 l 길이 만큼의 블록들을 체크 해 간다.

      => i-1칸과 높이가 다르다면 false / 이미 경사로가 놓여있다면 false / 주어진 범위를 벗어나는 경우 false

    (2) 이전 칸이 다음 칸보다 큰 경우 

      => 다음 칸(i)에서 l 길이 만큼의 블록들을 체크 해 간다.

      => i칸과 높이가 다르다면 false / 이미 경사로가 놓여있다면 false / 주어진 범위를 벗어나는 경우 false

 

 

#include <iostream>
#include <vector>
using namespace std;
int arr[100][100];
int n, l;

bool check(vector<int> &c) {
	vector<bool> existed(n, false);
	for (int i = 1; i < n; i++) {
		if (c[i] != c[i - 1]) {
			int diff = abs(c[i] - c[i - 1]);
			if (diff > 1) return false;
			if (c[i] > c[i - 1]) {
				for (int j = 0; j < l; j++) {
					if (i -1- j < 0) return false;
					if (c[i-1] != c[i -1 - j]) return false;
					if (existed[i - 1 - j]) return false;
					existed[i - 1 - j] = true;
				}
				
			}
			else if (c[i] < c[i - 1]) {
				for (int j = 0; j < l; j++) {
					if (i + j >= n) return false;
					if (c[i] != c[i + j]) return false;
					if (existed[i + j]) return false;
					existed[i + j] = true;
				}
			}
		}
	}
	return true;
}
int main() {
	int answer = 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++) {
		vector<int> a;
		for (int j = 0; j < n; j++) {
			a.push_back(arr[i][j]);
		}
		if (check(a)) answer++;
	}
	// 세로 체크
	for (int i = 0; i < n; i++) {
		vector<int> b;
		for (int j = 0; j < n; j++) {
			b.push_back(arr[j][i]);
		}
		if (check(b)) answer++;
	}
	cout << answer;
	return 0;
}