백준 14890번 | 경사로 (C++ 풀이)

  문제  

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

14890번: 경사로

---

  풀이  

• 사용 알고리즘 : 구현

꽤 까다로운 구현 문제였습니다.

​

저는 일단 입력을 받고 나서 데이터를 순서쌍 (칸의 높이, 같은 높이의 칸이 연속해서 인접해있는 개수) 로 바꿔서 처리했습니다. 예를 들어 3, 2, 2, 1, 2, 3 이 입력으로 들어온다면 (3,1), (2,2), (1,1), (2,1), (3,1) 로 바꾸는 식입니다.

​

이제 경우를 나눠서 봐보죠. 편의를 위해 저 위의 순서쌍을 (A[i].first, A[i].second)라고 부르겠습니다.

​

① 한 줄의 모든 칸의 높이가 같은 경우

이 경우는 당연히 가능하겠죠. 굉장히 편안한 길입니다.

​

② 인접한 두 칸의 높이 차가 2 이상인 경우

이 경우에는 당연히 안됩니다. 경사로의 높이는 무조건 1이니까요.

​

③ 인접한 두 칸 중, 왼쪽 칸의 높이가 오른쪽 칸의 높이보다 작은 경우

이때는 경사로를 설치해야겠죠. 경사로를 두기 위해서는 A[i].second가 경사로의 길이 l보다 크거나 같아야합니다.

​

④ 인접한 두 칸 중, 왼쪽 칸의 높이가 오른쪽 칸의 높이보다 큰 경우

이때도 역시 경사로를 설치해야겠죠. 경사로를 두기 위해서는 A[i + 1].second가 경사로의 길이 l 보다 크거나 같아야합니다.

추가적으로 이 경우에서는 생각해줘야 하는 것이 한개가 더 있습니다.

이런 경우입니다. 이 경우에는 순서쌍이 (2,1), (1,2), (2,1)과 같이 저장될텐데, 각 순서대로 A[0], A[1], A[2]라고 해보죠.

​

A[0].first > A[1].first 이므로, A[1].second의 값이 2보다 크거나 같은지를 보게 되는데, 일단 이를 만족하므로 넘어갑니다.

​

문제는 A[1].first < A[2].first 인 경우인데, A[1].second의 값이 경사로의 길이 l보다 크거나 같은지를 확인합니다. 이때 A[1].second의 값은 2 이므로 경사로의 길이 l 과 같기 때문에 가능하다고 판단할 수 있지만, 저 그림을 보면 아시겠지만 불가능합니다. 따라서 경사로를 설치하게 된다면 해당 칸의 second 값은 경사로의 길이 l 만큼 빼주어야 합니다. 즉, A[1].second - l 을 해주게 되면서 A[1].second의 값이 0으로 바뀌게 됩니다.

​

이렇게 되면 A[1].first < A[2].first 인 경우에도 문제가 없습니다. A[1].second의 값이 경사로의 길이 l 보다 작기 때문이죠. 따라서 불가능한 길이라는 것을 판단할 수 있습니다.

​

이제 각 행과 열에 대해 한 줄씩 위의 경우들로 나누어 생각하며 구현을 열심히 해주면 됩니다.

---

  코드  

#include <bits/stdc++.h> 
using namespace std;
const int INF = 2e9;
const int inf = 1e9;

int mmap[101][101];
vector<pair<int, int>> r[101];
vector<pair<int, int>> c[101];

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, l;
	cin >> n >> l;
	int ans = 0;
	for (int i = 0; i < n; i++) { 
		for (int j = 0; j < n; j++) {
			cin >> mmap[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (r[i].size() && r[i].back().first == mmap[i][j]) r[i].back().second++;
			else r[i].push_back({mmap[i][j], 1});
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (c[i].size() && c[i].back().first == mmap[j][i]) c[i].back().second++;
			else c[i].push_back({mmap[j][i], 1});
		}
	}
	for (int i = 0; i < n; i++) {
		int sizeR = r[i].size();
		if (sizeR == 1) {
			ans++;
			continue;
		}
		bool flag = false;
		for (int j = 0; j < sizeR - 1; j++) {
			if (abs(r[i][j].first - r[i][j + 1].first) >= 2) {
				flag = true;
				break;
			}
			if (r[i][j].first > r[i][j + 1].first) {
				if (r[i][j + 1].second >= l) {
					r[i][j + 1].second -= l;
				}
				else {
					flag = true;
					break;
				}
			}
			else if (r[i][j].first < r[i][j + 1].first) {
				if (r[i][j].second < l) {
					flag = true;
					break;
				} 
			}
		}
		if (!flag) ans++;
	}
	for (int i = 0; i < n; i++) {
		int sizeC = c[i].size();
		if (sizeC == 1) {
			ans++;
			continue;
		}
		bool flag = false;
		for (int j = 0; j < sizeC - 1; j++) {
			if (abs(c[i][j].first - c[i][j + 1].first) >= 2) {
				flag = true;
				break;
			}
			if (c[i][j].first > c[i][j + 1].first) {
				if (c[i][j + 1].second >= l) {
					c[i][j + 1].second -= l;
				}
				else {
					flag = true;
					break;
				}
			}
			else if (c[i][j].first < c[i][j + 1].first) {
				if (c[i][j].second < l) {
					flag = true;
					break;
				} 
			}
		}
		if (!flag) ans++;
	}
	cout << ans;
	return 0;
}