백준 14890번 경사로

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

14890번: 경사로

 

 

 

 

<접근방법>

시뮬레이션 문제입니다.

단순하게 하나하나 구현한다면 복붙한다해도 시간이 걸릴 것 입니다.

보통 이런 문제들은 생각을 살짝 바꾼다면 하나의 모듈에 여러 상황을 담을 수 있습니다.

 

행 오른쪽 경사로 탐색, 행 왼쪽 경사로 탐색, 열 위쪽 경사로 탐색, 열 아래쪽 경사로 탐색

 

문제에서 고려해야 할 상황입니다.

 

행과 열은 회전만 시켜주면 똑같은 것이고

오른쪽, 왼쪽은 뒤집으면 똑같은 것 입니다.

 

즉, 전처리로 저렇게 해주면 탐색 모듈은 하나만 있으면 됩니다.

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct point {
	int y, x;
};

int n, l, map[101][101];
int ans;

bool check(vector<int> v, bool visit[], int type) {
	for (int i = 0; i < n - 1; i++) {
		int val = v[i];
		int nval = v[i + 1];

		if (nval - val > 1) return false;
		if (nval - val == 1) {
			//경사로를 놓을 길이 체크
			int end;
			if (type == 0)	end = i - l + 1;
			else	end = i - l + 1;

			if (end < 0 || end >= n) return false;

			int start;
			if (type == 0)	start = i;
			else	start = i;

			//방문 체크
			for (int j = end; j <= start; j++) {
				if (visit[j])	return false;
			}

			//방문 처리
			for (int j = end; j <= start; j++) {
				visit[j] = true;
			}
		}
	}
	return true;
}

void simul_row(vector<int> v) {
	bool visit[101] = { false, };

	if (!check(v, visit, 0)) return;

	reverse(visit, visit + n);
	reverse(v.begin(), v.end());

	if (!check(v, visit, 0)) return;

	ans++;
}

void simul_col(vector<int> v) {
	bool visit[101] = { false, };

	if (!check(v, visit, 1)) return;

	reverse(visit, visit + n);
	reverse(v.begin(), v.end());

	if (!check(v, visit, 1)) return;

	ans++;
}

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

	for (int i = 0; i < n; i++) {
		vector<int> v;
		for (int j = 0; j < n; j++) {
			v.push_back(map[i][j]);
		}
		simul_row(v);
	}

	for (int j = 0; j < n; j++) {
		vector<int> v;
		for (int i = 0; i < n; i++) {
			v.push_back(map[i][j]);
		}
		simul_col(v);
	}


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

 

 

---

 

 

<느낀 점>

-구현 복잡성