백준 14890_경사로

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

14890번: 경사로

마찬가지로 시뮬레이션 문제이다.

행열을 뒤집어서 체크하고 싶으면 입력을 받을 때, a[i][j] 뿐 아니라 b[j][i]로 뒤집어서 같이 받으면 커버 가능하다.

 

구현할 때, 경사로의 조건 중에서 높이 차이가 1만 허용한다는 사실을 반드시 명심해야 한다.

이를 통해 1이상이 차이가 나면 결코 길이 만들어질 수 없다.

 

나는 문제 접근을 실제 경사로를 만들어 해당 길이 내림차순 또는 오름차순으로 한방향으로 정리되면 경로가 만들어진 것으로 판단하려 했으나 실제 경사로를 만드는 과정이 굉장히 애매하고 길어져서 다른 분들의 풀이를 참고하였다.

그 결과, 실제 경사로를 만들지 않고 만들어서 경로를 지나갈 수 있는지만 확인하면 되었다.

어차피 경로는 한 번 지나가면 끝이기에 굳이 경사로를 만들어서 다시 탐색할 필요가 없는 것이다.

 

따라서 경사로를 통해 경로를 만들 수 있는 지 확인해야 하는 경우는 다음의 2 가지 이다.

1. 오른쪽 내리막길 > 경사로를 만들 때는 이전 값과 비교해서 해당 지점의 값이 갑자기 작아졌을 경우
(앞으로의 지점 경로 l개를 확인한다, 탐색 후에 탐색 index를 i+l-1로 간다)

2. 왼쪽 내리막길 < 경사로를 만들 때는 이전 값과 비교해서 해당 지점의 값이 갑자기 커졌을 경우
(지나온 지점 경로 l개를 확인한다)

두 경우 모두 구간을 생성하여 탐색하는데 0보다 작은 지점부터 시작하거나 n보다 큰 지점에서 시작한다면 그만한다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, l, ans;
int a[100][100], b[100][100];

void solution(int row, int a[100][100]) {
	bool c[100] = { false, };
	int temp = a[row][0];
	for (int i = 0; i < n; i++) {
		if (a[row][i] != temp) {
			// 차가 1보다 클 경우
			if (abs(a[row][i] - temp) > 1) return; 

			// > 오른쪽 경사로
			if (a[row][i] < temp) { 
				int num = a[row][i];
				// j => i 부터 i+ㅣ-1 까지 경로 가능한지
				for (int j = i; j <= i + l - 1; j++) {
					// 넘어가면 종료
					if (j >= n || c[j]) return;
					c[j] = true;
					if (a[row][j] != num) return;
				}
				// 다음으로 탐색
				i = i + l - 1;
				if (i >= n) break;
			}

			// < 왼쪽 경사로
			else { 
				int num = a[row][i-1];
				// j => i-1 부터 i-l 까지 경로 가능한지
				for (int j = i - 1; j >= i - l; j--) {
					// 넘어가면 종료
					if (j < 0 || c[j]) return;
					c[j] = true; 
					if (a[row][j] != num) return;
				}
			}
			// 값 기록
			temp = a[row][i];
		}
	}
	ans++;
}

int main() {
	cin >> n >> l;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
			b[j][i] = a[i][j]; // 행열 뒤집은 것(열 방향 경로 탐색)
		}
	for (int i = 0; i < n; i++) {
		solution(i, a);
		solution(i, b);
	}
	cout << ans << endl;
	return 0;
}