BOJ : 14890 경사로

---

[BOJ 14890(G3) 리뷰]

삼성 SW역량테스트 기출문제다. 요즘 하나씩 풀고있다.

이 문제도 예전에 풀다가 포기했던 문제인데 지금 풀리는걸 보니 실력이 늘고있긴 한가보다. 신기하다.

문제 조건은 다음과 같다.

• 길을 건너기 위해서는 칸의 높이가 같아야 한다.
• 높이가 다를때는 경사로를 놓아 길을 지날 수 있다. 경사로의 높이는 1로 고정되어 있다.
• 경사로는 입력받은 L의 길이만큼 놓을 수 있다. 이것보다 적게,크게 놓을 수 없다.
• 경사로가 겹치면 안된다

나는 문제를 풀기위하여 천천히 하나하나씩 시뮬레이션하며 경우의 수를 생각해보았다.

일단은 2N만큼의 길을 탐색해야 하므로, 행 우선 탐색을 수행 한 후에 동일한 코드에 행과 열의 위치만 바꿔 열 우선 탐색을 수행 했다.

그리고 값을 하나 하나씩 비교한다음 현재의 값이 이전값과 1이 차이난다면 그때부터 경사로를 놓을 수 있는 조건인지 확인하기 시작한다. 이 때, 경사로를 놓을 수 있는 조건은 경사로를 놓으려 하는 L길이의 칸이 높이가 같아야하며 이전에 경사로가 놓인적이 없어야 한다. 이 조건을 여러 변수와 반복문을 이용하여 구현했다.

코드를 보면 알겠지만, 재사용성을 고려하지 않은 무식한 코드이지만 어쨌든 답은 맞았으니 만족한다...

/*
	20.12.30
	BOJ : 14890 경사로 (https://www.acmicpc.net/problem/14890)
	구현
*/

#include <iostream>
using namespace std;

int N, L;
int map[101][101];
bool vis[101];

int main() {
	cin >> N >> L;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}

	int ans = 0;

	//행 탐색
	for (int i = 0; i < N; i++) {
		int check = 1;
		int prev = map[i][0];
		for (int n = 0; n < N; n++)
			vis[n] = 0;

		for (int j = 1; j < N; j++) {
			if (map[i][j] > prev) { //
				if (j - L < 0 || abs(map[i][j]-prev) != 1) { //범위 벗어나거나 차이가 2 이상이면 경사로 못놓음
					check = 0;
					break;
				}

				int st = j - L;
				int value = map[i][st];
				bool isSame = 1;
				for (int k = st; k < j; k++) {
					if (map[i][k] != value || vis[k]) {
						isSame = 0;
						break;
					}
				}

				if (st - 1 >=0 && map[i][st - 1] > value) {
					isSame = 0;
				}


				if (!isSame) {
					check = 0;
					break;
				}
				else {
					vis[j-1] = 1;
				}
			}
			else if (map[i][j] < prev) {
				if (j + L -1 >= N || abs(map[i][j] - prev) != 1) { //범위 벗어나거나 차이가 2 이상이면 경사로 못놓음
					check = 0;
					break;
				}

				int ed = j + L - 1;
				int value = map[i][j];
				bool isSame = 1;
				for (int k = j; k <= ed; k++) {
					if (map[i][k] != value || vis[k]) {
						isSame = 0;
						break;
					}
				}

				if (ed +1  <N && map[i][ed + 1] > value) {
					isSame = 0;
				}

				if (!isSame) {
					check = 0;
					break;
				}
				else {
					vis[ed] = 1;
				}
			}
			prev = map[i][j];
		}

		if (check)
		{
			ans++;
		}
	}

	//열 탐색
	for (int i = 0; i < N; i++) {
		int check = 1;
		int prev = map[0][i];
		for (int n = 0; n < N; n++)
			vis[n] = 0;
		for (int j = 1; j < N; j++) {
			if (map[j][i] > prev) { //
				if (j - L < 0 || abs(map[j][i] - prev) != 1) { //범위 벗어나거나 차이가 2 이상이면 경사로 못놓음
					check = 0;
					break;
				}

				int st = j - L;
				int value = map[st][i];
				bool isSame = 1;
				for (int k = st; k < j; k++) {
					if (map[k][i] != value || vis[k]) {
						isSame = 0;
						break;
					}
				}

				if (st - 1 >= 0 && map[st-1][i] > value) {
					isSame = 0;
				}

				if (!isSame) {
					check = 0;
					break;
				}
				else {
					vis[j-1] = 1;
				}
			}
			else if (map[j][i] < prev) {
				if (j + L - 1 >= N || abs(map[j][i] - prev) != 1) { //범위 벗어나거나 차이가 2 이상이면 경사로 못놓음
					check = 0;
					break;
				}

				int ed = j + L - 1;
				int value = map[j][i];
				bool isSame = 1;
				for (int k = j; k <= ed; k++) {
					if (map[k][i] != value ||vis[k]) {
						isSame = 0;
						break;
					}
				}

				if (ed + 1 < N && map[ed + 1][i] > value) {
					isSame = 0;
				}

				if (!isSame) {
					check = 0;
					break;
				}
				else {
					vis[ed] = 1;
				}
			}
			prev = map[j][i];
		}

		if (check)
		{
			ans++;
		}
	}

	cout << ans;
}