[BOJ 14890] 경사로 (C++)

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

14890번: 경사로

#include <vector>
#include <iostream>
#include <cmath>
#include <cstring>
#define ROW 0
#define COL 1
using namespace std;

int graph[100][100];
bool isksr[100];

bool findRoad(int num, int rc, int N, int L) {
	memset(isksr, false, sizeof(isksr));
	if (rc == 0) {
		int prev = graph[num][0];
		for (int i = 1; i < N; i++) {
			int cnt = L;
			if (abs(prev - graph[num][i]) > 1)
				return false;
			else if (graph[num][i] - prev == 1) {		//올라가는 경사로 놓을때
				int start = i - 1;
				while (cnt>0 && start>=0) {
					if (graph[num][start] != prev || isksr[start])		//경사로 설치가 가능한 곳을 체크
						return false;
					start--;
					cnt--;
				}
				if (cnt != 0)
					return false;
				for (int j = start + 1; j < start + 1 + L; j++)
					isksr[j] = true;
			}
			else if (graph[num][i] - prev == -1) {   //내려가는 경사로 놓을 때
				int end = i;
				while (cnt>0 && end <= N) {
					if (graph[num][end] != graph[num][i])
						return false;
					end++;
					cnt--;
				}
				if (cnt != 0)
					return false;
				for (int j = i; j < i + L; j++)
					isksr[j] = true;	
				i = i + L - 1;
			}
			prev = graph[num][i];
		}
	}
	else {
		int prev = graph[0][num];
		for (int i = 1; i < N; i++) {
			int cnt = L;
			if (abs(prev - graph[i][num]) > 1)
				return false;
			else if (graph[i][num] - prev == 1) {
				int start = i - 1;
				while (cnt > 0 && start >= 0) {
					if (graph[start][num] != prev || isksr[start])		
						return false;
					start--;
					cnt--;
				}
				if (cnt != 0)
					return false;
				for (int j = start + 1; j < start + 1 + L; j++)
					isksr[j] = true;
			}
			else if (graph[i][num] - prev == -1) { 
				int end = i;
				while (cnt > 0 && end <= N) {
					if (graph[end][num] != graph[i][num])
						return false;
					end++;
					cnt--;
				}
				if (cnt != 0)
					return false;
				for (int j = i; j < i + L; j++)
					isksr[j] = true;
				i = i + L - 1;
			}
			prev = graph[i][num];
		}
	}
	return true;
}

int main() {
	int N, L;
	int ans = 0;
	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> graph[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		if (findRoad(i, ROW, N, L))
			ans++;
		if (findRoad(i, COL, N, L))
			ans++;
		//rows(i) 탐색
		//cols(i) 탐색
	}
	cout << ans << "\n";
	return 0;
}

compact & sophisticated 하게 짜지 못함..

 

시뮬레이션 문제.

한 줄을 탐색하고 그걸 2N 번 반복한다. 

탐색하는 방법은=> 바로 앞에 있었던 애와 지금 애를 비교해서, 둘 간의 차(now-prev) 가 1이면 올라가는 경사로를 건설해야 한다. -1 이면 내려가는 경사로를 건설해야 된다. 둘 간의 차가 abs(1) 이상이면 false 리턴.

올라가는 경사로의 경우 경사로 설치가 가능한지 체크한다.

- prev로부터 맨 앞쪽 방향으로 L번 이동하여 탐색하면서 (prev와 같은 높이인지 & 경사로를 설치하지 않은 곳인지) 체크하고, 이런 것이 L개 존재하면 경사로 설치했다고 isksr 배열에 체크한다. 

내려가는 경사로의 경우 다음과 같이 체크한다.

- now로부터 맨 뒤쪽 방향으로 L번 이동하여 탐색하면서 (now와 같은 높이인지) 체크하고, 이런 것이 L개 존재하면 마찬가지로 방문 표시를 해준다. 그 다음 탐색할 곳을 경사로 설치한 제일 마지막 부분의 바로 뒤로 구성한다.

경사로 설치가 가능한지 체크하는 부분에서, 조건이 맞아떨어지지 않으면 바로 false를 리턴한다.

 

나는 row, col 별로 코드를 따로 두었는데(i,j 바꾼 똑같은 코드) 이럴 필요 없이 vector로 각 한 줄을 저장해서 탐색하는 방법을 취하면 코드 길이를 줄일 수 있다.

 

그리고 경사로 구성하는 조건을 구현할 때, 

if (v[i-1] < v[i]) //더 높을 경우

 for (j=1; j<=L; j++) //L번 탐색

  if (i-j<0) return false //구간 벗어남

  if (v[i-1] != v[i-j]) return false//높이가 같지 않음

  if (visited(i-j)) return false //경사로를 또 놓는 경우

 visited[i-j]=true; 

이런 식으로 i를 기준으로 for문으로 L번 탐색하면서 조건을 체크하는 방식을 취하면 더 깔끔하게 짤 수 있다.