[백준 14890번] 경사로 C++

[14890번 경사로]
https://www.acmicpc.net/problem/14890

이 문제에서의 핵심은 하나의 길(행 혹은 열)을 갈 때, 높이가 1만 차이나는 턱을 오르내릴 수 있는지 구현하는 것이었다.

time complexity: O(N^2)
space complexity: O(N^2)

풀이 방법

1.

moveRight() 메서드를 만들고 row를 1~N까지 돌면서 moveRight()로 끝까지 걸어갈 수 있는지 판단한다.
moveDown() 메서드를 만들고 column을 1~N까지 돌면서 moveDown()으로 끝까지 걸어갈 수 있는지 판단한다.

2.

move***() 메서드는 3가지 경우로 나뉘어 전진할 수 있는지 판단한다.

1. 다음 블럭의 값이 내가 서있는 블럭의 값보다 클 때

a)

블럭 값의 차이가 1 초과라면 올라갈 수 없으니 0을 반환한다.
b)

차이가 1이라면, 지금까지 세어 온 블럭의 개수가 L의 값과 같거나 크다면(즉, 충분한 블럭이 있다면) 나의 위치를 다음 블럭(즉, 올라간다)으로 옮기고, 지금까지 센 블럭의 개수를 1로 초기화한다(옮긴 내 위치에 경사로가 설치되어 있지 않기 때문에 블럭 한 개를 확보한 셈이다).
만약 블럭의 개수가 충분치 않다면 0을 반환한다.

2. 다음 블럭의 값이 내가 서있는 블럭의 값보다 작을 때

a)

남아있는 블럭의 개수가 L보다 작다면(내려가기 위한 경사로를 놓을 블럭이 충분치 않다면) 0을 반환한다.

b)

내 위치 다음 블럭부터 L개의 블럭을 전진하며, 블럭의 값이 모두 (내 블럭 값) - 1과 같은 게 아니라면 0을 반환한다(길이가 L인 경사로를 놓을 블럭의 높이가 모두 같아야 하기 때문에).

c)

블럭의 값이 모두 (내 블럭 값) - 1과 같다면, 나의 위치를 경사로가 끝나는 지점으로 옮기고, j or i의 값(moveRight or moveDown)을 (j or i) + L - 1으로 갱신한다.
(for문 특성상 ++j/++i이 수행될 것이며, 자연스럽게 (j or i) + L로 값이 증가한다)

이 갱신으로 인하여, 경사로가 끝난 지점 바로 다음 지점부터 다시 비교가 가능하다(나의 위치를 경사로가 끝난 지점이라는 것을 잊지 말아야 한다).

지금까지 센 블럭의 개수는 0으로 초기화한다(옮긴 내 위치는 경사로가 끝나는 지점이기 때문에, 경사로를 놓을 수 있는 블럭이 아니다).

3. 값이 같다면 지금까지 센 블럭의 개수를 1 늘리고 나의 위치를 전진시킨다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int ans = 0;
int N;
int map[101][101];
int L;

int moveRight(int &r, int &c) {
	int cnt = 1;
	int val = map[r][c]; // the value of my block

	for(int j=c+1;j<=N;++j) {
		// the next block bigger
		if(map[r][j] > val) {
			if(map[r][j] != val + 1) {
				return 0;
			}

			if(cnt >= L) {
				val = map[r][j];
				cnt = 1;
			} else {
				return 0;
			}
		}
		// the next block smaller
		else if(map[r][j] < val) {
			if(N - j + 1 < L) {  // minimum length not enough
				return 0;
			}

			for(int k=j;k<=j+L-1;++k) {
				if(map[r][k] != val - 1) {
					return 0;
				}
			}

			val = map[r][j+L-1];
			j = j + L - 1;
			cnt = 0;
		}
		// the same
		else {
			cnt++;
			val = map[r][j];
		}
	}

	return 1;
}

int moveDown(int &r, int &c) {
	int cnt = 1;
	int val = map[r][c];

	for(int i=r+1;i<=N;++i) {
		if(map[i][c] > val) {
			if(map[i][c] != val + 1) {
				return 0;
			}

			if(cnt >= L) {
				val = map[i][c];
				cnt = 1;
			} else {
				return 0;
			}
		} else if(map[i][c] < val) {
			if(N - i + 1 < L) {
				return 0;
			}
			for(int k=i;k<=i+L-1;++k) {
				if(map[k][c] != val - 1) {
					return 0;
				}
			}
			val = map[i+L-1][c];
			i = i + L - 1;
			cnt = 0;
		} else {
			cnt++;
			val = map[i][c];
		}
	}

	return 1;
}

void sol() {
	for(int i=1;i<=N;++i) {
		int c = 1;
		if(moveRight(i,c)) {
			ans++;
		}
	}

	for(int j=1;j<=N;++j) {
		int r = 1;
		if(moveDown(r,j)) {
			ans++;
		}
	}
}

int main(void) {
	ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

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

	cout << ans << '\n';
	
	return 0;
}