[BOJ] 14890 : 경사로 - travelbeeee

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

---

[ 알고리즘풀이 ]

 시뮬레이션 문제입니다. row 기준으로 경사로를 세울 수 있는지 없는지 check 하고 col 기준으로 경사로를 세울 수 있는지 없는지 체크했습니다. 이때, 2차원 bool 배열 2개를 이용해, 경사로를 이미 세운 곳과 세우지 않은 곳을 구별했습니다.

 row 기준으로 경사로를 세울 수 있는지 없는지 check하는 과정입니다. brute 하게 열들을 순회하며 높이의 차이가 생긴 순간 경사로를 지어가며 문제를 해결했습니다.

void checkRow() {
	for (int i = 0; i < N; i++) {
		bool ansCheck = true;
		for (int j = 0; j < N - 1; j++) {
			int diff = map[i][j] - map[i][j + 1];
			if (diff == 0)
				continue;
			else if (diff == 1) {
				if (N - j - 1 < L) { // 공간부족 -> 경사로 못세움.
					ansCheck = false;
					break;
				}
				for (int k = 0; k < L; k++) {
					if(map[i][j + 1] == map[i][j + 1 + k]){
						rowCheck[i][j + 1 + k] = true;
					}
					else { //경사로 못지음.
						ansCheck = false;
						j = N;
						break;
					}

				}
			}
			else if (diff == -1) {
				if (j + 1 < L) { // 공간부족 -> 경사로 못세움.
					ansCheck = false;
					break;
				}
				for (int k = 0; k < L; k++) {
					if (rowCheck[i][j - k] == false && map[i][j] == map[i][j - k]) {
						rowCheck[i][j - k] = true;
					}
					else {
						ansCheck = false;
						j = N;
						break;
					}
				}
			}
			else {
				ansCheck = false;
				break;
			}
		}
		if(ansCheck)
			ans++;
	}
}

 col 도 마찬가지입니다. 전체 코드는 아래와 같습니다.

#include<iostream>
using namespace std;

int N, L, map[100][100] = {}, ans = 0;
bool rowCheck[100][100], colCheck[100][100] = {};

void checkRow() {
	for (int i = 0; i < N; i++) {
		bool ansCheck = true;
		for (int j = 0; j < N - 1; j++) {
			int diff = map[i][j] - map[i][j + 1];
			if (diff == 0)
				continue;
			else if (diff == 1) {
				if (N - j - 1 < L) { // 공간부족 -> 경사로 못세움.
					ansCheck = false;
					break;
				}
				for (int k = 0; k < L; k++) {
					if(map[i][j + 1] == map[i][j + 1 + k]){
						rowCheck[i][j + 1 + k] = true;
					}
					else { //경사로 못지음.
						ansCheck = false;
						j = N;
						break;
					}

				}
			}
			else if (diff == -1) {
				if (j + 1 < L) { // 공간부족 -> 경사로 못세움.
					ansCheck = false;
					break;
				}
				for (int k = 0; k < L; k++) {
					if (rowCheck[i][j - k] == false && map[i][j] == map[i][j - k]) {
						rowCheck[i][j - k] = true;
					}
					else {
						ansCheck = false;
						j = N;
						break;
					}
				}
			}
			else {
				ansCheck = false;
				break;
			}
		}
		if(ansCheck)
			ans++;
	}
}

void checkCol() {
	for (int j = 0; j < N; j++) {
		bool ansCheck = true;
		for (int i = 0; i < N - 1; i++) {
			int diff = map[i][j] - map[i + 1][j];
			if (diff == 0)
				continue;
			else if (diff == 1) {
				if (N - i - 1 < L) { // 공간부족 -> 경사로 못세움.
					ansCheck = false;
					break;
				}
				for (int k = 0; k < L; k++) {
					if (map[i + 1][j] == map[i + 1 + k][j]) {
						colCheck[i + 1 + k][j] = true;
					}
					else { //경사로 못지음.
						ansCheck = false;
						i = N;
						break;
					}

				}
			}
			else if (diff == -1) {
				if (i + 1 < L) { // 공간부족 -> 경사로 못세움.
					ansCheck = false;
					break;
				}
				for (int k = 0; k < L; k++) {
					if (colCheck[i - k][j] == false && map[i][j] == map[i - k][j]) {
						colCheck[i - k][j] = true;
					}
					else {
						ansCheck = false;
						i = N;
						break;
					}
				}
			}
			else {
				ansCheck = false;
				break;
			}
		}
		if (ansCheck)
			ans++;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> L;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];

	checkRow();
	checkCol();
	cout << ans;
}

---