[BOJ] 14890 경사로

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

Note

N x N 지도가 주어졌을 때 l길이의 경사로를 놓아 지나갈 수 있는 경로의 갯수를 출력해준다.

경사로를 놓기 위해서는 높이의 차이가 1이어야한다. 또한 경사로는 겹쳐서 놓을 수가 없다.
범위를 벗어나서는 안된다. 경사로의 개수는 무제한이다.
위 조건을 만족 하기 위해서 경사로를 놓은 위치를 기억해야한다. 각 줄에 대해서 독립 시행이기때문에
과거의 결과를 저장하면 안됬었다.
세로와 가로가 같은 방식의 알고리즘이지만 한개의 함수로 묶어서 구현하면 생각보다 구현이 복잡해 나눠서 구현했다.
BFS/DFS가 없는 순수한 구현 문제이기때문에 쉽다.

알고리즘

1. N x N 지도와 경사로의 길이 l을 입력 받는다.
2. 0 ~ N 까지 가로와 세로에 대해서 경사로를 놓는 모습을 시뮬레이션 한다.
   1. 현재 시행에 대해서 경사로를 놓은 위치를 저장하기 위한 변수를 선언한다.
   2. 현재위치와 다음 위치의 높이가 다른 경우 경사로를 놓을수 있는지 판단한다.
   - 높이가 1 증가하는 경우 다음칸 부터 l 칸이 높이가 같은지 판별해 경사로를 놓는 판단을 한다.
   - 높이가 1 감소하는 경우 현재 칸부터 뒤로 l 칸이 높이가 같은지 판별해 경사로를 놓는 판단을 한다.
   - 이외의 경우 경사로를 놓을 수 없다.
   3. 경사로가 겹치지 않는다면 경사로를 놓은 다음 위치로 옮긴 후 반복을 진행한다.
3. 경사로를 놓은 수를 출력한다.

소스코드

#include <iostream>

using namespace std;

const short MAX = 100;

short board[MAX][MAX];

bool checkVertical(const int row, int max, int len)
{
	bool stair[MAX] = {};

	for (int cur = 0; cur < max;)
	{
		int next = cur + 1;
		if (next == max)
			break;

		if (board[cur][row] == board[next][row])
			cur = next;
		else if (board[cur][row] - 1 == board[next][row])
		{
			if (cur + len >= max)
				return false;

			short origin = board[next][row];

			for (int i = 0; i < len; i++)
				if (stair[next + i] || origin != board[next + i][row])
					return false;
				else
					stair[next + i] = true;

			cur += len;
		}
		else if (board[cur][row] + 1 == board[next][row])
		{
			if (next - len < 0)
				return false;

			short origin = board[cur][row];

			for (int i = 0; i < len; i++)
				if (stair[cur - i] || origin != board[cur - i][row])
					return false;
				else
					stair[cur - i] = true;

			cur = next;
		}
		else
			return false;
	}

	return true;
}

bool checkHorizontal(int col, int max, int len)
{
	bool stair[MAX] = {};

	for (int cur = 0; cur < max;)
	{
		int next = cur + 1;
		if (next == max)
			break;

		if (board[col][cur] == board[col][next])
			cur = next;
		else if (board[col][cur] - 1 == board[col][next])
		{
			if (cur + len >= max)
				return false;

			short origin = board[col][next];

			for (int i = 0; i < len; i++)
				if (stair[next + i] || origin != board[col][next + i])
					return false;
				else
					stair[next + i] = true;

			cur += len;

		}
		else if (board[col][cur] + 1 == board[col][next])
		{
			if (next - len < 0)
				return false;

			short origin = board[col][cur];

			for (int i = 0; i < len; i++)
				if (stair[cur - i] || origin != board[col][cur - i])
					return false;
				else
					stair[cur - i] = true;

			cur = next;
		}
		else
			return false;
	}

	return true;
}

int main()
{
	int n, l;
	int res = 0;

	cin >> n >> l;

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

	for (int i = 0; i < n; i++)
	{
		res += checkVertical(i, n, l);
		res += checkHorizontal(i, n, l);
	}

	cout << res;

	return 0;
}

2019-04-01 00:43:46에 Tistory에서 작성되었습니다.