백준 14890 경사로 C풀이

경사로를 설치할 수 있는지 묻는 문제이다.

처음부터 끝까지 모두 부드럽게 연결되어야 하기 때문에 시작점은 y=0 이거나 x=0 인 지점부터 가로세로 한번씩만 하면 된다.

문제의 조건은 다음과 같다.

1. 높이차이는 1을 초과하면 안된다.

2. 경사로는 평평한 곳에만 놓을 수 있다.

3. 경사로의 길이만큼 놓을 땅이 필요하다.

4. 경사로는 겹칠 수 없다.

 

지도의 크기가 100x100 이므로 무리 없이 끝낼 수 있다.

 

문제 해결은 다음과 같다.

1. 현재보다 높은땅이 나오면 지금 땅에 경사로를 설치할 수 있는지 확인한다.

2. 현재보다 낮은땅이 나오면 다음 땅에 경사로를 설치할 수 있는지 확인한다.

3. 무리없이 설치하고 끝에 도착했다면 count한다.

 

두 방향을 하나의 함수로 만들 수도 있지만, 그냥 두 개로 노가다했다...

그게 편하잖아..

 

전체코드

#include <stdio.h>
#define MAX_N 100
int T, N, X;
int Map[MAX_N+1][MAX_N+1];

int abs(int x) {
	if (x < 0) return -x;
	return x;
}
//y=0 부터 y=N-1 까지 세로로 판단
int updown(int x) {
	int y = 0;
	int num = 1;
    //끝에 도착할때까지
	while (y+1 < N) {
		//같은 높이
		if (Map[y][x] == Map[y + 1][x]) {
        //현재 높이의 땅이 몇개나 있는지
			num++;
			y++;
			continue;
		}// 높이차이 1 초과 -> 무조건 실패
		else if (abs(Map[y + 1][x] - Map[y][x]) > 1) return 0;
		//더 높은 곳으로 이동할 때
		else if (Map[y + 1][x] > Map[y][x]) {
			//경사로 설치 가능한 땅 길이면 다음칸 넘어가기 가능
			if (num >= X) {
				y++;
                //땅 수 초기화
				num = 1;
			}
            //설치 불가능하면 실패
			else {
				return 0;
			}
		}
		//낮은곳으로 갈때
		else {
			int next = y + 1;
			int nnum = 1;
			//다음칸이랑 같은 높이의 칸 셈
			while (1) {
				if (next  >= N) {
					//끝까지 닿은 상황
                    //경사로 길이만큼 땅이 있지 않다면 실패
					if (nnum < X) return 0;
                    //설치 가능하다면 성공
					return 1;
				}
                //끝이 아닌 상황
                //땅 높이가 다를 경우 스탑
				if (Map[next + 1][x] != Map[next][x]) {
                //땅 길이가 경사로 길이에 못미칠때 실패
					if (nnum < X) return 0;
                    //경사로 마지막 부분으로 위치 초기화, 땅 수 초기화
                    //마지막 부분의 다음칸으로 초기화할 경우 땅 높이가 다른 경우 생각해줘야함
					num = 0;
					y = y+X;
					break;
				}
                //다음칸과 같은 높이의 칸 수 증가
				next++;
				nnum++;
			}
		}

	}
	return 1;
}
//가로 체크, 로직 동일
int leftright(int y) {

	int x = 0;
	int num = 1;
	while (x + 1 < N) {
		//같은 높이
		if (Map[y][x] == Map[y ][x+1]) {
			num++;
			x++;
			continue;
		}// 높이차이 1 초과
		else if (abs(Map[ y][x+1] - Map[y][x]) > 1) return 0;
		//더 높은 곳으로 이동할 때
		else if (Map[y][x+1] > Map[y][x]) {
			//활주로 가능
			if (num >= X) {
				x++;
				num = 1;
			}
			else {
				return 0;
			}
		}
		//낮은곳으로 갈때
		else {
			int next = x + 1;
			int nnum = 1;
			//다음칸이랑 같은 칸 셈
			while (1) {
				if (next  >= N) {
					//끝까지 닿은 상황
					if (nnum < X) return 0;
					return 1;
				}
				if (Map[y][next+1] != Map[y][next]) {
					if (nnum < X) return 0;
					num = 0;
					x = x + X;
					break; 
				}
				next++;
				nnum++;
			}
		}

	}
	return 1;
}

int solve() {
	int ret = 0;
	for (int i = 0; i < N; i++) {
		ret += updown(i);
	}
	for (int i = 0; i < N; i++) {
		ret += leftright(i);
	}




	return ret;
}

int main() {
		scanf("%d %d", &N, &X);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				scanf("%d", &Map[i][j]);
			}
		}
		int ans = solve();
		printf("%d\n", ans);
	return 0;
}