[백준] 14890번: 경사로

구현의 실력이 일취월장하고 있다.

처음에 문제 읽을 때만해도 이걸 어떻게 구현하나 난감해 했는데, 단 한 번의 제출만에 성공해버렸다.(소오름...)

우선 문제를 최대한 간단하게 만들어서, 유효한 길인지 판단하는 방법을 단순화했다.

 

1. Line 추출

괜히 이차원으로 접근하는 코드를 만들면 구현하는 내가 힘들다...ㅠ

한 줄로 만들어서 공통으로 적용하는 코드를 만들면 이해하기 쉽고, 직관적이라 수정하기에 쉽다.

 

2. 유효성 파악

유효하지 않은 패턴을 파악해보니 크게 아래와 같다.

 

1) 높이 차이가 1보다 큰 경우

2) 경사로를 놓을만한 충분한 공간이 없는 경우

3) 경사로 배치가 중복되는 경우

 

1, 2번의 경우 비교적 판단하기 쉬우나, 경사로 배치가 중복되는 경우를 처리하기 까다로웠다.

상대적인 높이 비교로 이렇게 내리막길이 될 수도 있고, 오르막길이 될 수도 있기 때문이다.

이를 한 번에 평가하려니 머리가 터질 거 같았다.

그래서 내리막길 따로, 오르막길 따로 카운트하기로 했다.

(항상 마음에 새기자. 어려운 문제는 쪼개서 생각해보기로)

 

이는 특히 유용했던 방식이었던 게,

내리막길의 경우 앞에서부터 인덱스를 키워가며 접근하면 내리막길이 필요하다는 것을 인지하는 시점에는 아직 경사로를 배치할 수 있는지 알 수가 없기 때문이다.

 

인덱스나 분기 설정을 비동기적으로 풀다보면 코드가 상당히 복잡해지기 때문에 이를 지양했다.

 

그래서 경사로 필요성과 경사로 배치 방식을 동시에 판단할 수 있도록

앞 인덱스로부터 접근하여 오르막길을 파악한 뒤, 뒤 인덱스로부터 접근하여 오르막길을 각각 평가하였다.

어차피 뒤 인덱스로부터 접근하여 파악한 오르막길은 곧 내리막길이다.

대신 뒤 인덱스로부터 접근하며 오르막길을 파악할 때는 중복성 평가를 같이 해줬다.

경사로를 이중으로 배치할 수 없기 때문이다.

 

3. 유효성 여부에 따라 카운트에 포함

 

 

이렇게 문제를 쪼개서 고민한 덕분에 문제 난이도에 비해 상당히 간결하고 직관적인 코드 작성이 가능했다. 🙃

#include <iostream>
#include <vector>

using namespace std;
int n, l;

vector<int> extract_line(int start, int dir, vector<vector<int>> arr) {
	vector<int> line(n);
	if(dir == 0) {
		for(int i = 0;i < n;i++) {
			line[i] = arr[start][i];
		}
	}
	else {
		for(int i = 0;i < n;i++) {
			line[i] = arr[i][start];
		}
	}
	return line;
}

bool block(vector<int> line) {
	vector<bool> blocks(n, false);
	int base_floor = line[0];
	int cnt = 1;
	int success = true;
	for(int block = 1;block < n;block++) {
		if (!success) break;
		if(base_floor == line[block]) {
			cnt++;
		}
		else if(base_floor < line[block]) {
			if(base_floor + 1 == line[block] && cnt >= l) {
				for(int j = 1;j <= l;j++) {
					blocks[block - j] = true;
				}
			}
			else {
				// 높이 차이가 1보다 큰 경우와 경사로를 놓을만한 공간이 없는 경우
				success = false;
			}
			base_floor = line[block];
			cnt = 1;
		}
		else {
			base_floor = line[block];
			cnt = 1;
		}
	}

	if(!success) {
		return success;
	}

	base_floor = line[n - 1];
	cnt = 1;
	for(int block = n - 2;block >= 0;block--) {
		if (!success) break;
		if(base_floor == line[block]) {
			cnt++;
		}
		else if(base_floor < line[block]) {
			if(base_floor + 1 == line[block] && cnt >= l) {
				for(int j = 1;j <= l;j++) {
					if(blocks[block + j]) {
						success = false;
						break;
					}
					blocks[block + j] = true;
				}
			}
			else {
				// 높이 차이가 1보다 큰 경우와 경사로를 놓을만한 공간이 없는 경우
				success = false;
			}
			base_floor = line[block];
			cnt = 1;
		}
		else {
			base_floor = line[block];
			cnt = 1;
		}
	}

	return success;
}

void print_line(vector<int> &line) {
	for(int i = 0;i < n;i++) {
		cout << line[i];
	}
	cout << endl;
}

int main() {
	int answer = 0;
	cin >> n >> l;
	vector<vector<int>> arr(n, vector<int>(n));
	for(int i = 0;i < n;i++) {
		for(int j = 0;j < n;j++) {
			cin >> arr[i][j];
		}
	}


	for(int i = 0;i < n;i++) {
		vector<int> line = extract_line(i, 0, arr);
		// print_line(line);
		bool success = block(line);
		// cout << success << endl;
		if(success) answer++;
	}

	for(int i = 0;i < n;i++) {
		vector<int> line = extract_line(i, 1, arr);
		// print_line(line);
		bool success = block(line);
		// cout << success << endl;
		if(success) answer++;
	}

	cout << answer << '\n';
}