[C++} 백준 14890 경사로

문제 링크

---

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

14890번: 경사로

 

 

문제 접근

---

점 (i, j)와 (i, j + 1)의 비교의 경우의 수는 다음과 같다.

1. 높이의 차가 2 이상인 경우

2. 같은 높이인 경우

3. 차가 1일때, 오르막인 경우

4. 차가 1일때, 내리막인 경우

 

높이의 차가 2인 경우, 해당 길은 지날 수 없다.

까다로운 부분은 오르막, 내리막의 경우인데, 낮은 지대에 경사로의 크기 L을 수용할 만한 공간이 있음을 체크해야한다.

 

- (i, j + 1)이 오르막인 경우, (i, j)가 더 낮은 지대이므로 (i, j)부터 뒤로 가면서 낮은 지대의 갯수가 L보다 크거나 같으면 이동 가능

 

- (i, j + 1)이 내리막인 경우, (i, j + 1)이 더 같은 지대이므로, (i, j + 1)부터 앞으로 가면서 낮은 지대의 갯수가 L보다 크거나 같으면 이동 가능

 

또 다른 중요한 점은 내리막과 오르막이 연달아 있는 경우에서 경사로를 겹쳐서 놓는 경우는 허가되지 않는다는 것이다. 따라서 visit 배열을 통해 경사로가 놓인 위치를 표시해줘야한다.

 

 

소스 코드

---

#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100
using namespace std;
int N, L, map[MAX][MAX], visit[MAX];

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

int solve() {
	int differ, ret = 0, low_area = 0;
	for (int i = 0; i < N; ++i) {
		memset(visit, 0, sizeof(visit));
		// 가로 검사
		for (int j = 1; j < N; ++j) {
			differ = map[i][j - 1] - map[i][j];
			if (abs(differ) > 1) break; // 차이가 2 이상이면 갈 수 있는 길이 아님
			
			// 오르막인 경우
			if (differ < 0) {
				low_area = 0;
				for (int l = j - 1; l >= 0; --l) { // j가 높은 지대이므로 j-1이전을 카운트
					if (visit[l] || map[i][l] != map[i][j - 1]) break;
					++low_area;
				}
				if (low_area >= L) { // 다리놓을 공간이 충분하므로 L개만큼 방문 표시하자
					low_area = L;
					for (int l = j - 1; l >= 0 && low_area > 0; --l, --low_area)
						visit[l] = 1;
				}
				else {
					break;
				}
			}

			// 내리막인 경우
			else if (differ > 0) { // j부터 낮은 지대이다.
				low_area = 0;
				for (int l = j; l < N; ++l) {
					if (visit[l] || map[i][l] != map[i][j]) break;
					++low_area;
				}
				if (low_area >= L) { // 다리놓을 공간이 충분하므로 L개만큼 방문 표시하자
					low_area = L;
					for (int l = j; l < N && low_area > 0; ++l, --low_area)
						visit[l] = 1;
				}
				else break;
			}
			// break되지 않고 여기까지왔다면 갈 수 있는 길임
			if (j == N - 1) ++ret;
		}
		memset(visit, 0, sizeof(visit));
		// 세로 검사
		for (int j = 1; j < N; ++j) {
			differ = map[j - 1][i] - map[j][i];
			if (abs(differ) > 1) break; // 차이가 2 이상이면 갈 수 있는 길이 아님

			// 오르막인 경우
			if (differ < 0) {
				low_area = 0;
				for (int l = j - 1; l >= 0; --l) { // j가 오르막이므로 j-1부터 본다.
					if (visit[l] || map[l][i] != map[j - 1][i]) break;
					++low_area;
				}
				if (low_area >= L) { // 다리놓을 공간이 충분하므로 L개만큼 방문 표시하자
					low_area = L;
					for (int l = j - 1; l >= 0 && low_area > 0; --l, --low_area)
						visit[l] = 1;
				}
				else break;
			}

			// 내리막인 경우
			else if (differ > 0) {
				low_area = 0;
				for (int l = j; l < N; ++l) { // j부터 낮은 지대임
					if (visit[l] || map[l][i] != map[j][i]) break;
					++low_area;
				}
				if (low_area >= L) { // 다리놓을 공간이 충분하므로 L개만큼 방문 표시하자
					low_area = L;
					for (int l = j; l < N && low_area > 0; ++l, --low_area)
						visit[l] = 1;
				}
				else break;
			}
			// break되지 않고 여기까지왔다면 갈 수 있는 길임
			if (j == N - 1) ++ret;
		}
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	input();
	cout << solve();
	return 0;
}

개발 환경 : VS2019

질문, 지적 환영합니다.