[BOJ] 14890번 경사로

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

14890번: 경사로

 

아이디어

행과 열에 한 줄에 대하여 양 옆으로 한번씩 조사를 하면서 길이 될지 조사를 함

 

1, 행

- 왼쪽에서 오른쪽으로 가는 길을 조사를 하고 올라가는 경우에 대하여 길이 l에 대하여 조사를 함 

 

- 내려가는 길에 대하여는 높이차이가 1인 경우에만 길조건 조사를 함

 

- 마찬가지로 오른쪽에서 왼쪽으로 가는 길을 조사를 마찬가지 방법으로 수행을 함

 (이때, 왼쪽에서 오른쪽으로 가면서 올라가기 위해 경사로를 놓은 부분을 표시하고 오른쪽에서 왼쪽으로 가는 길에 대하여 이미 경사로가 놓아져 있다면 경사로를 놓지 못함으로 길이 안된다고 판단)

 

2, 열

- 행과 마찬가지 방법으로 방향을 위에서 아래, 아래에서 위로 판단을 하여 길의 판단 여부를 함

 

소스코드

#include <cstdio>
using namespace std;

int n,l;

int map[101][101];

bool row_check(int row_num) {

	//왼쪽에서 오른쪽으로
	int location_check[101] = {0,};
	int temp;
	int cnt = 0;
	temp = map[row_num][0];
	cnt = 1;
	for (int i = 1; i < n; i++) {
		//같은 경우
		if (temp == map[row_num][i]) {
			cnt++;
		}
		//내려가는 경우
		else if (temp > map[row_num][i]) {
			if (temp - map[row_num][i] > 1) {
				return false;
			}
			cnt = 1;
			temp = map[row_num][i];
		}
		//올라가는 경우
		else {
			if (map[row_num][i] - temp > 1) {
				return false;
			}

			if (cnt < l) {
				return false;
			}
			else {
				for (int j = i - 1; j >= i - l; j--) {
					if (location_check[j] == 1) return false;
					location_check[j] = 1;
				}

				cnt = 1;
				temp = map[row_num][i];
			}

		}
	}


	//오른쪽에서 왼쪽으로
	temp = map[row_num][n-1];
	cnt = 1;
	for (int i = n-2; i >= 0; i--) {
		//같은 경우
		if (temp == map[row_num][i]) {
			cnt++;
		}
		//내려가는 경우
		else if (temp > map[row_num][i]) {
			if (temp - map[row_num][i] > 1) {
				return false;
			}
			cnt = 1;
			temp = map[row_num][i];
		}
		//올라가는 경우
		else {
			if (map[row_num][i] - temp > 1) {
				return false;
			}

			if (cnt < l) {
				return false;
			}
			else {
				for (int j = i+1 ; j  <= i + l; j++) {
					if (location_check[j] == 1) return false;
					location_check[j] = 1;
				}
				cnt = 1;
				temp = map[row_num][i];
			}

		}
	}
	
	return true;

}

bool col_check(int col_num) {

	//위에서 아래로
	int location_check[101] = { 0, };
	int temp;
	int cnt = 0;
	temp = map[0][col_num];
	cnt = 1;
	for (int i = 1; i < n; i++) {
		//같은 경우
		if (temp == map[i][col_num]) {
			cnt++;
		}
		//내려가는 경우
		else if (temp > map[i][col_num]) {
			if (temp - map[i][col_num] > 1) {
				return false;
			}
			cnt = 1;
			temp = map[i][col_num];

		}
		//올라가는 경우
		else {
			if (map[i][col_num] - temp > 1) {
				return false;
			}

			if (cnt < l) {
				return false;
			}
			else {
				for (int j = i - 1; j >= i - l; j--) {
					if (location_check[j] == 1) return false;
					location_check[j] = 1;
				}
				cnt = 1;
				temp = map[i][col_num];
			}

		}
	}

	temp = map[n-1][col_num];
	cnt = 1;
	for (int i = n - 2; i >= 0; i--) {
		//같은 경우
		if (temp == map[i][col_num]) {
			cnt++;
		}
		//내려가는 경우
		else if (temp > map[i][col_num]) {
			if (temp - map[i][col_num] > 1) {
				return false;
			}
			cnt = 1;
			temp = map[i][col_num];
		}
		//올라가는 경우
		else {
			if (map[i][col_num] - temp > 1) {
				return false;
			}
			if (cnt < l) {
				return false;
			}
			else {
				for (int j = i + 1; j <= i + l; j++) {
					if (location_check[j] == 1) return false;
					location_check[j] = 1;
				}
				cnt = 1;
				temp = map[i][col_num];
			}

		}
	}

	return true;

}

int main(){
	int res = 0;

	scanf("%d %d", &n, &l);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	for (int i = 0; i < n; i++) {
		if (row_check(i)) res++;
		if (col_check(i)) res++;
	}

	printf("%d\n", res);

	return 0;
}