[백준/BOJ] 백준 14890번 : 경사로

www.acmicpc.net/problem/14890

14890번: 경사로

모든 길들을 확인하며 지나갈 수 있는 길인지 확인한다. 해당 길에서 현재 높이와 다음 높이의 차이가 1보다 크다면 지날 수 없는 길이고, 높이 차이가 1 일 때는 경사로를 놓았을 때 범위를 벗어나는지 확인하고, 경사로를 높을 수 있는지도 확인을 하여 지날 수 있는 길인지 확인한다. 경사로를 놓는 구간은 int install[100][100]로 표시해 경사로 위에 경사로가 배치되는 것을 방지하였다.

 

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;

int n, l;
int board[100][100];
int install[100][100];

int Solve()
{
	int ret = 0;

	bool thisload;

	memset(install, 0, sizeof(install));
	
	//세로 길들을 확인
	for (int i = 0; i < n; i++)
	{
		thisload = true;
		for (int j = 0; j < n - 1; j++)
		{
			//높이 차이가 1보다 클때
			if (abs(board[i][j] - board[i][j + 1]) > 1)
			{
				thisload = false;
				break;
			}

			//다음 높이가 현재 높이보다 1 더 클때
			if (board[i][j] + 1 == board[i][j + 1])
			{
				//경사로를 높을수 없을때(범위를 벗어날때)
				if (j - (l - 1) < 0)
				{
					thisload = false;
					break;
				}

				for (int k = 0; k < l; k++)
				{
					//경사로를 높을수 없을때
					if (board[i][j - k] != board[i][j] || install[i][j - k] == 1)
					{
						thisload = false;
						break;
					}
					//경사로 설치 표시
					install[i][j - k] = 1;
				}

				//지날 수 있는 길이 아닐때
				if (thisload == false)
					break;
			}

			//다음 높이가 현재 높이보다 1 더 낮을때
			if (board[i][j] == board[i][j + 1] + 1)
			{
				if (j + 1 + (l - 1) >= n)
				{
					thisload = false;
					break;
				}

				for (int k = 0; k < l; k++)
				{
					if (board[i][j + 1 + k] != board[i][j + 1] || install[i][j + 1 + k] == 1)
					{
						thisload = false;
						break;
					}
					install[i][j + 1 + k] = 1;
				}
				if (thisload == false)
					break;
			}
		}

		//지날 수 있는 길을 찾았을때
		if (thisload == true)
		{
			ret++;
		}
	}

	memset(install, 0, sizeof(install));
	
	//가로 길들을 확인
	for (int j = 0; j < n; j++)
	{
		thisload = true;
		for (int i = 0; i < n - 1; i++)
		{
			if (abs(board[i][j] - board[i + 1][j]) > 1)
			{
				thisload = false;
				break;
			}

			if (board[i][j] + 1 == board[i + 1][j])
			{
				if (i - (l - 1) < 0)
				{
					thisload = false;
					break;
				}

				for (int k = 0; k < l; k++)
				{
					if (board[i - k][j] != board[i][j] || install[i - k][j] == 1)
					{
						thisload = false;
						break;
					}
					install[i - k][j] = 1;
				}
				if (thisload == false)
					break;
			}

			if (board[i][j] == board[i + 1][j] + 1)
			{
				if (i + 1 + (l - 1) >= n)
				{
					thisload = false;
					break;
				}

				for (int k = 0; k < l; k++)
				{
					if (board[i + 1 + k][j] != board[i + 1][j] || install[i + 1 + k][j] == 1)
					{
						thisload = false;
						break;
					}
					install[i + 1 + k][j] = 1;
				}
				if (thisload == false)
					break;
			}
		}
		if (thisload == true)
		{
			ret++;
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int input;

	cin >> n >> l;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> input;
			board[i][j] = input;
		}

	cout << Solve();

	return 0;
}