<Baekjoon> #14890 구현_경사로 c++

💬IDEA

• 경사로를 놓을 수 있는 곳인가 체크할 때, 가로, 세로 경사로를 둘 다 체크해야 한다. 처음에는 (y,x)좌표만변경해서 체크하는 함수를 2개 만들었는데, 굳이 그렇게 하지 않고 map에 값을 입력 받을 때 값을 가로부터 저장하는 것, 세로부터 저장하는 것 이렇게 두 개의 map을 만드는 것으로 수정했다.
• 높이가 다른 지점이 나왔을 때, 길이 L인 경사로를 만들기 위해서 이 지점 앞에 얼마만큼의 길이의 길이 있는가 체크하기 위해 beforeRoad변수를 둔다.
  
  예를들어 첫 번째 그림에서 화살표 지점에서 beforeRoad=3이고, 경사로의 길이 L=2보다 크기 때문에 경사로를 만들 수 있다
  두 번째 그림에서 화살표 지점에 높이 2인 칸이 있다고 하면 앞에 이미 길이 L=2인 경사로가 있기 때문에 beforeRoad=1이다. 따라서 새로운 경사로를 만들 수 없다.

👩‍💻1. input Data

• 앞서 말했듯이 가로부터 입력, 세로부터 입력되는 2개의 map을 만든다

	map1 = vector<vector<int>>(N+1, vector<int>(N+1));
	map2 = vector<vector<int>>(N+1, vector<int>(N+1));
	int h;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> h;
			map1[i][j] = h;
			map2[j][i] = h;
		}
	}

👩‍💻2. make Road

• 현재 칸과 다음 칸의 높이가 같다면 beforeRoad를 늘린다

if (map[i][j] == map[i][j + 1]) beforeRoad++;

• 현재 칸보다 다음 칸이 1 높고 beforeRoad가 L보다 크거나 같다면 계속 진행하고(경사로를 만들고) beforeRoad=1로 만들어준다
beforeRoad를 0이 아닌 1로 만들어주는 이유는 그림을 그려 생각해보면 쉽다
  

• 현재 칸보다 다음 칸이 1 낮다면 현재 위치 j에서 L칸 떨어진 곳까지 다음칸의 높이와 같은지 확인한다
  

bool canMakeRoad(vector<vector<int>>map, int y, int x) {
	int standard = map[y][x+1];
	for (int j = x + 1; j <= x + L; j++)
		if (map[y][j] != standard) return false;
	return true;
}

여기서 beforeRoad를 0으로 만들어주는 이유는 높이 확인이 끝나면 j는 j+L부터 다시 탐색하게 만들어준다. 그림에서 j+L과 j+L+1의 높이는 같으므로 beforeRoad=1이 되고 j=j+L+1인 상태에서 탐색을 시작할 때는 원래 앞에 아무 길도 없었던 것처럼 다시 beforeRoad=1이 된다.

말로 설명하기 조금 복잡한데, 만약 j+L까지 높이 확인이 끝난 후 j+L+1부터 탐색하게 하고 beforeRoad=1로 만들어주면 되지 않겠냐 할 수도 있는데 j+L+1지점으로 왔을 때 높이가 2이고 L=1같은 경우로 주어졌을 때 문제가 발생한다.

문제 자체는 쉽지만 이런 것들을 생각하면 좀 까다로운 것 같다

전체코드

#include <iostream>
#include <vector>

using namespace std;

int N, L;
vector<vector<int>> map1;
vector<vector<int>> map2;

bool canMakeRoad(vector<vector<int>>map, int y, int x) {
	int standard = map[y][x+1];
	for (int j = x + 1; j <= x + L; j++)
		if (map[y][j] != standard) return false;
	return true;
}

int makeRoad(vector<vector<int>> map) {
	int cnt = 0;
	
	for (int i = 0; i < N; i++) {
		int beforeRoad = 1;
		bool build = true;
		for (int j = 0; j < N - 1; j++) {
			if (map[i][j] == map[i][j + 1]) beforeRoad++;
			else {
				//뒤에가 한 칸 큰 경우
				if (map[i][j] + 1 == map[i][j + 1]) {
					if (beforeRoad >= L)
						beforeRoad = 1;
					else {
						build = false; break;
					}
				}
				//뒤에가 한 칸 작은 경우
				else if (map[i][j] - 1 == map[i][j + 1]) {
					if (canMakeRoad(map, i, j)) {
						j = j + L - 1;
						beforeRoad = 0;
					}
					else {
						build = false; break;
					}
				}
				//차이가 1이 아닌경우
				else {
					build = false; break;
				}
			}
		}
		if (build) cnt++;
	}
	return cnt;
}

void init() {
	cin >> N >> L;
	map1 = vector<vector<int>>(N+1, vector<int>(N+1));
	map2 = vector<vector<int>>(N+1, vector<int>(N+1));
	int h;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> h;
			map1[i][j] = h;
			map2[j][i] = h;
		}
	}
}

int main() {
	init();
	cout << makeRoad(map1) + makeRoad(map2) << endl;
	return 0;
}