[구현] 14890 경사로 C++

Seunghyeon·2023년 1월 27일

백준 문제 푼다.

목록 보기

8/21

풀이

내가 풀이한 방법은 문제에 나와있는 그대로 구현으로 옮긴 것이다.

그래서 Map의 가로줄을 전부 검사한 후 세로줄을 검사한다.

한칸 한칸 확인하면서 옆칸과의 높이차이를 계산한다.

그리고 그 차이가 2면 그 줄은 불가. 0이면 바로 통과

1일때가 문제인데 이때는 올라가는 경사로인지, 내려가는 경사로인지에 따라 구분하였다.

경사로를 둘 때는 자리가 충분한지 확인하고, 경사로를 두면서 visited 배열에 체크한다.

경사로를 둔 곳은 경사로를 겹쳐서 둘 수 없기 때문에 visited로 검사한다.

코드

#include <bits/stdc++.h>

using namespace std;

// 판 넓이
int n;
// 경사로의 길이
int l;
int Map[100][100] = { 0, };
int sum = 0;
int visited[100][100] = { 0, };
bool flag = true;
// 경사로의 높이는 1, 길이는 L
// 경사로를 놓은곳에는 또 놓을 수 없음.
// 높이차이가 1일 경우에만 가능.
// 경사로가 Map 범위를 넘어가는 경우.

void solve()
{
	// 가로줄 확인하기
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1; j++)
		{
			flag = true;
			int dif = abs(Map[i][j] - Map[i][j + 1]);
			// i,j 와 i,j+1의 차이가 2이상일 경우 무조건 불가능함.
			if (dif >= 2)
			{
				flag = false;
				break;
			}
			// 옆칸과 차이가 1일 때
			else if (dif == 1)
			{
				// 높아지는 경우일 때
				if (Map[i][j] < Map[i][j + 1])
				{
					// 여유가 있어야 경사로를 배치할 수 있음.
					if (j >= (l - 1))
					{
						// for문을 무사히 통과하면 경사로 배치
						for (int k = j; k > j - l; k --)
						{
							if (Map[i][j] != Map[i][k] || visited[i][k])
							{
								flag = false;
								break;
							}
						}

						if (flag == false)
							break;

						for (int k = j; k > j - l; k--)
						{
							visited[i][k] = 1;
						}
					}
					else
					{
						flag = false;
						break;
					}
				}
				// 낮아지는 경우일 때
				if (Map[i][j] > Map[i][j + 1])
				{
					if (n - j > l)
					{
						for (int k = j+1; k <= j + l; k++)
						{
							if (Map[i][j+1] != Map[i][k] || visited[i][k])
							{
								flag = false;
								break;
							}
						}
						if (flag == false)
							break;

						for (int k = j + 1; k <= j + l; k++)
						{
							visited[i][k] = 1;
						}
					}
					else
					{
						flag = false;
						break;
					}
				}
			}
			// 평평할 때
			else if( dif == 0 )
			{
				continue;
			}
		}
		if (flag == true)
			sum++;
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			visited[i][j] = 0;
		}
	}

	// 세로줄 확인하기
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1; j++)
		{
			flag = true;
			int dif = abs(Map[j][i] - Map[j+1][i]);
			// j,i 와 j+1,i의 차이가 2이상일 경우 무조건 불가능함.
			if (dif >= 2)
			{
				flag = false;
				break;

			}
			// 옆칸과 차이가 1일 때
			else if (dif == 1)
			{
				// 높아지는 경우일 때
				if (Map[j][i] < Map[j+1][i])
				{
					// 여유가 있어야 경사로를 배치할 수 있음.
					if (j >= (l - 1))
					{
						for (int k = j; k > j - l; k--)
						{
							if (Map[j][i] != Map[k][i] || visited[k][i])
							{
								flag = false;
								break;
							}
						}
						if (flag == false)
							break;
						for (int k = j; k > j - l; k--)
						{
							visited[k][i] = 1;
						}
					}
					else
					{
						flag = false;
						break;
					}
				}
				// 낮아지는 경우일 때
				if (Map[j][i] > Map[j+1][i])
				{
					if (n - j > l)
					{
						for (int k = j + 1; k <= j + l; k++)
						{
							if (Map[j+1][i] != Map[k][i] || visited[k][i])
							{
								flag = false;
								break;
							}
						}
						if (flag == false)
							break;
						for (int k = j + 1; k <= j + l; k++)
						{
							visited[k][i] = 1;
						}

					}
					else
					{
						flag = false;
						break;
					}
				}
			}
			// 평평할 때
			else if (dif == 0)
			{
				continue;
			}
		}
		if (flag == true)
			sum++;
	}

}
int main()
{
	cin >> n >> l;

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

	solve();
	cout << sum;
	return 0;
}