[SWEA] 4014. 활주로 건설

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH

SW Expert Academy

 행과 열 모두 같은 방법으로 검사하므로 행으로만 설명해보자면 현재 위치와 다음 위치에 높이가 다르면 경사로를 이용하여 활주로를 건설할 수 있는지를 판별하게 됩니다. 만약 차이가 1이 넘으면 경사로를 설치해도 활주로를 만들 수 없습니다. 만약 다음 위치가 높이가 높다면 현재의 위치부터 X-1까지의 높이가 모두 같아야 합니다. 다음 위치가 더 낮다면 다음 위치부터 X만큼의 높이가 같아야 합니다. 이것은 check를 통해서 검사하게 됩니다. 

	#include<iostream>
	#include<algorithm>
	using namespace std;
	int tc, n, X,ans;
	int map[20][20];
	int check = 0;
	bool InRange(int y, int x)
	{
	return 0 <= x && x < n && 0 <= y && y < n;
	}
	//행 검사
	int check_slide_row(int y, int x)
	{
	int xx = x;
	int h = map[y][x];
	//다음 과의 높이 차가 1이 아니면 항공로 설치 불가
	if (abs(map[y][x] - map[y][x + 1]) != 1)
	return -1;
	//다음 높이가 더 큰 경우
	if (map[y][x] < map[y][x + 1])
	{
	//현재 위치가 높이가 더 크면 안됨
	if (check)
	return -1;
	for (int i = 0; i < X; i++)
	{
	if (!InRange(y, xx) || map[y][xx] != h)
	return -1;
	xx--;
	}
	return 0;
	}
	else
	{
	xx++;
	h = map[y][xx];
	for (int i = 0; i < X; i++)
	{
	if (!InRange(y, xx) || map[y][xx] != h)
	{
	return -1;
	}
	xx++;
	}
	return X - 1;
	}
	}
	//열 검사
	int check_slide_col(int y, int x)
	{
	int yy = y;
	int h = map[y][x];
	if (abs(map[y][x] - map[y + 1][x ]) != 1)
	return -1;
	if (map[y][x] < map[y + 1][x])
	{
	if (check)
	return -1;
	for (int i = 0; i < X; i++)
	{
	if (!InRange(yy, x) || map[yy][x] != h)
	return -1;
	yy--;
	}
	return 0;
	}
	else
	{
	yy++;
	h = map[yy][x];
	for (int i = 0; i < X; i++)
	{
	if (!InRange(yy, x) || map[yy][x] != h)
	return -1;
	yy++;
	}
	return X - 1;
	}
	}
	int main(void)
	{
	cin >> tc;
	for (int t = 1; t <= tc; t++)
	{
	cin >> n >> X;
	ans = 0;
	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++)
	{
	check = 0;
	bool check2 = true;
	for (int j = 0; j < n - 1; j++)
	{
	if(check > 0)
	check--;
	if (map[i][j] != map[i][j + 1])
	{
	int k = check_slide_row(i, j);
	if (k == -1)
	{
	check2 = false;
	break;
	}
	if (k == X - 1)
	check = X + 1;
	j += k;
	}
	}
	if (check2)
	{
	ans++;
	}
	}
	for (int j = 0; j < n; j++)
	{
	check = 0;
	bool check2 = true;
	for (int i = 0; i < n - 1; i++)
	{
	if(check>0)
	check--;
	if (map[i][j] != map[i + 1][j])
	{
	int k = check_slide_col(i, j);
	if (k == -1)
	{
	check2 = false;
	break;
	}
	if (k == X - 1)
	check = X + 1;
	i += k;
	}
	}
	if (check2)
	{
	ans++;
	}
	}
	cout <<'#'<<t<<' '<< ans << endl;
	}
	}

view raw [SWEA] 4014.cpp hosted with ❤ by GitHub