[ 백준 14890 ] 경사로 / SWEA 활주로 건설 문제

# 문제링크

www.acmicpc.net/problem/14890

14890번: 경사로

이건 SW Expert Academy에서 풀었던 활주로 건설 문제와 같은 문제다! 한 번 풀었기 때문에 접근법을 알고있어서 금방 풀었다. 시뮬레이션 문제는 어렵다기 보다는.. 정신을 똑바로 차리는 게 가장 중요한 것 같다..

 

일차원 배열 arr 을 하나 만들어서 한 줄씩 살펴보았다. 그렇게 모든 맵을 탐색하고 나서, 90도 회전해서 한 번 더 검사해준다. 그럼 세로 방향을 따로 만들지 않아도 된다..

 

 

# 제출 코드 

 

#include <cstdio>
#include <cstring>
using namespace std;

int map[101][101];
int N, L;
int arr[101];
bool chk[101];
int backup[101][101];

bool check_arr() {
	memset(chk, 0, sizeof(chk));
	for (int i = 0; i < N - 1; i++) {
		int tmp = arr[i] - arr[i + 1];
		if (tmp > 1 || tmp < -1) return false; // 높이 차이가 1 이상 -> 못건넘
		else if (tmp == 1) { // 높이가 낮아짐 
			if (i + L >= N)return false; // 범위
			for (int s = i + 1; s < i + L; s++) {
				if (arr[s] != arr[s + 1]) return false;
			}
			// 경사로 놓을 수 있으면 chk 배열에 저장
			for (int s = i + 1; s <= i + L; s++) {
				if (chk[s] == true) return false; // 이미 경사로 있음 
				chk[s] = true;
			}
		}
		else if (tmp == -1) { // 높이가 높아짐
			if (i - L + 1 < 0) return false;
			for (int s = i - L + 1; s < i; s++) {
				if (arr[s] != arr[s + 1])return false;
			}
			// 경사로 놓을 수 있으면 chk 배열에 저장
			for (int s = i - L + 1; s <= i; s++) {
				if (chk[s] == true) return false; // 이미 경사로 있음 
				chk[s] = true;
			}
		}
	}
	return true;
}

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

void rotate() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			backup[N - j - 1][i] = map[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			map[i][j] = backup[i][j];
		}
	}
}

int main() {
	Input();
	int ans = 0;
	for (int i = 0; i < 2; i++) {

		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				arr[x] = map[y][x];
			}
			bool ret = check_arr();
			if (ret) ans++;
		}
		rotate(); // 90 도 돌려서 세로도 검사
	}
	printf("%d\n", ans);
}