BOJ 14890 : 경사로 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/14890

 

이후 설명 및 입/출력은 링크 참고

 

먼저 경사로가 설치 가능한지, 1차원 배열에 대해서만 check함수를 만들고, for문을 이용해서 N번 check하자.

이때, 가로 배열, 세로 배열에 대해서 따로 check를 만들 필요 없이, MAP을 회전 시킨 후 check 하면 된다.

sum = 0;
for (int i = 0; i < N; i++)
{
	sum += check(MAP[i]);
	sum += check(TMAP[i]); /* TMAP[c][r] == MAP[r][c] */
}

 

이제 경사로가 설치 가능한지 check해보자.

 

먼저 arr에 대해 inverse한 배열이 필요하다.

for (int i = 0; i < N; i++) inverse[i] = arr[N - i - 1];

 

arr는 →로 가면서 낮아지는 구간이 있는지만 check한다.

inverse는 ←로 가면서 낮아지는 구간이 있는지 check한다.

 

즉, arr의 높아지는 구간은 inverse에서 그 역할을 대신하게 된다.

 

이때,  arr에서 경사로가 설치 가능하다면, visit 배열로 경사로를 설치 했다는 것을 표시하자.

이러면 inverse에서 경사로를 설치 할 때, arr에 이미 설치되어있는 경우에 경사로 설치가 불가능한 것을 알 수 있다.

 

경사로 설치 여부는 아래와 같이 검사한다.

 

1) 높이가 같으면 continue

2) 높이의 차가 2 이상이면 false

3) i보다 i + 1번 째가 낮을 때, 경사로 길이 L이 설치 가능한지 check (모두 평평한지, N을 넘지 않는 지)

4) 평평하다면 visit으로 경사로 설치 표시.

5) inverse 배열에 대해 1) ~ 3) 반복, 경사로 설치 시 visit을 보고 설치 가능한지 check.

 

최종 코드에 주석을 표시하였다.

#include <stdio.h>

#define MAX (100 + 20)

int N, L;
int MAP[MAX][MAX];
int TMAP[MAX][MAX];

void input()
{
	scanf("%d %d", &N, &L);

	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			scanf("%d", &MAP[r][c]);
			TMAP[c][r] = MAP[r][c];
		}
	}
}

int abs(int a, int b)
{
	return (a > b) ? a - b : b - a;
}

int isFlat(int* arr, int start, int end) 
{
	int value = arr[start];
	for (int i = start + 1; i <= end; i++)
		if (value != arr[i]) return 0;

	return 1;
}

int check(int* arr)
{
	int inverse[MAX] = { 0 };
	int visit[MAX] = { 0 };
	int visit_inverse[MAX] = { 0 };

	for (int i = 0; i < N; i++) inverse[i] = arr[N - i - 1];

	for (int i = 0; i < N - 1; i++)
	{
		if (arr[i] == arr[i + 1]) continue; /* 1) 높이가 같으면 continue */
		if (abs(arr[i], arr[i + 1]) > 1) return 0; /* 2) 높이의 차가 2 이상이면 flase */
		if (arr[i] > arr[i + 1]) /* 3) i + 1이 작을 때, */
		{
			if (i + L == N) return 0; /* 경사로의 범위가 N을 넘으면 false */
			if (isFlat(arr, i + 1, i + L) == 0) return 0; /* i + 1 ~ i + L 까지 평평한지 체크 */

			for (int k = i + 1; k <= i + L; k++) visit[k] = 1; /* 경사로 설치 */
		}
	}

	/* inverse 경사로 설치를 위해 visit inverse */
	for (int i = 0; i < N; i++) visit_inverse[i] = visit[N - i - 1]; 

	for (int i = 0; i < N - 1; i++)
	{
		/* 1) ~ 3) */
		if (inverse[i] == inverse[i + 1]) continue; 
		if (abs(inverse[i], inverse[i + 1]) > 1) return 0;
		if (inverse[i] > inverse[i + 1])
		{
			if (i + L == N) return 0;
			if (isFlat(inverse, i + 1, i + L) == 0) return 0;

			for (int k = i + 1; k <= i + L; k++) /* 이미 설치된 경사로면 false */
				if (visit_inverse[k]) return 0;
		}
	}

	return 1;
}

int main(void)
{
	int sum;

	input();

	sum = 0;
	for (int i = 0; i < N; i++)
	{
		sum += check(MAP[i]);
		sum += check(TMAP[i]);
	}

	printf("%d\n", sum);

	return 0;
}