백준 14890 - 경사로

문제링크

• 백준 14890

문제설명

• 크기가 N x N 인 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.
• 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.
• 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.
  • 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
  • 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
  • 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.
• 아래와 같은 경우에는 경사로를 놓을 수 없다.
  • 경사로를 놓은 곳에 또 경사로를 놓는 경우
  • 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
  • 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
  • 경사로를 놓다가 범위를 벗어나는 경우
• 지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

문제접근

• 높이가 변할 때 경사로를 두어야 하는 위치를 찾는다.
  • 예를 들어, L=2 이고 {3, 2, 2, 1, 1, 1, 1, 2} 라는 길이 있을 때 (1, -1), (3, -1), (7, 1) 처럼 표시한다. 데이터의 의미는 (인덱스, 높이변화량) 을 나타내고 1, 3번째 칸에서 -1만큼 높이감소가 있고 7번째 칸에서 1만큼 높이 증가가 있다는 것을 의미한다.
• 인덱스와 높이 변화를 보고 경사로를 두어야 하는 범위를 찾는다.
  • 1번째 칸에서 -1만큼 감소했으므로 해당 길에는 1, 2번째 칸에 경사로를 두어야 한다.
  • 3번째 칸에서 -1만큼 감소했으므로 해당 길에는 3, 4번째 칸에 경사로를 두어야 한다.
  • 7번째 칸에서 1만큼 증가했으므로 해당 길에는 5, 6번째 칸에 경사로를 두어야 한다.
• 경사로를 두어야 하는 범위가 길의 길이를 벗어나거나 이미 경사로를 둔 곳이라면 지나갈 수 없는 길이다.

구현

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#define MAX_N 100
#define UP 1
#define DOWN -1
using namespace std;

int N, L;
int board[MAX_N][MAX_N];

void input()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> N >> L;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> board[r][c];
		}
	}
}

int checkRoad(vector<int> road)
{
	int ref = road[0];
	vector<pair<int, int>> v;
	for (int i = 1; i < road.size(); i++) {
		int diff = abs(ref - road[i]);
		if (diff >= 2) return 0;
		if (ref > road[i]) v.push_back(make_pair(i, DOWN)); // i번에서 1만큼 감소
		else if (ref < road[i]) v.push_back(make_pair(i, UP)); // i번에서 1만큼 증가
		ref = road[i];
	}

	if (v.size() == 0) return 1; // 평탄한 경우
	vector<int> used(N, 0);
	for (int i = 0; i < v.size(); i++) {
		pair<int, int> cinfo = v[i];
		if (cinfo.second == UP) {
			int startIdx = cinfo.first - L;
			if (startIdx < 0) return 0;
			for (int i = 0; i < L; i++) {
				if (used[i + startIdx] == 1) return 0;
				used[i + startIdx] = 1;
			}
		}
		else if (cinfo.second == DOWN) {
			int startIdx = cinfo.first;
			if (startIdx + L > N) return 0;
			for (int i = 0; i < L; i++) {
				if (used[i + startIdx] == 1) return 0;
				used[i + startIdx] = 1;
			}
		}
	}
	return 1;
}

int solution()
{
	int ret = 0;
	for (int r = 0; r < N; r++) {
		vector<int> road;
		for (int c = 0; c < N; c++) road.push_back(board[r][c]);
		ret += checkRoad(road);
	}

	for (int c = 0; c < N; c++) {
		vector<int> road;
		for (int r = 0; r < N; r++) road.push_back(board[r][c]);
		ret += checkRoad(road);
	}
	return ret;
}

int main()
{
	input();
	cout << solution() << endl;
	return 0;
}