[백준] 14890번: 경사로

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

14890번: 경사로

 

문제 이해

이 문제도 SWEA에 있는 문제이다.

근데 백준에 있는 문제가 더 친절한 것 같다.

예외상황을 더 정리를 잘해준 것 같다.

물론 그냥 내가 SWEA 를 볼 때 문제를 제대로 안읽었을 가능성도 있다.ㅎㅎ

 

아무튼, 그냥 이건 무식한 시뮬레이션 문제이다.

처음에 배열에다가 행, 열을 복사해서 같은 함수로 그 줄이 통과할 수 있는 줄인지 확인하려고 했는데,

복잡하게 꼬여서 그냥 행 체크, 열 체크 함수를 별도로 만들어버렸다.

 

저번에 2차원배열 문제도 그렇고 이것도 그렇고 괜히 머리 쓴다고 시간 날리지 말고 그냥 별도로 작성하자! 

 (나는 못하니까)

 

아무튼 그래서 Check_R과 Check_C는 행,열이 뒤바뀌었을 뿐 같다.

 

아 그리고 이 문제에서 내가 처음에 간과한 것은, 

행에서 경사로를 지은 곳에 열에서 경사로를 또 지을 수 있다는 점이다!

이걸 처음에 다 안된다고 해줬더니 답이 안나오더라 ^^... 문제의 오류인 것인가..

 

Check_R()

i부터 N-2까지 그 다음 것 (i+1 / N-1)을 비교한다.

• 둘이 같으면 갈 수 있으니 continue,

 

• i 번째보다 i+1 가 클 경우,
  • 높이 차이가 2이상이다 -> 갈 수 없음
  • i번째부터 앞으로 L칸, 즉 i-L+1칸까지 같아야 한다. 이때, 하나하나 비교하기 전에, i-L+1칸이 범위 내에 존재하는지를 먼저 확인한다. 존재 안하면 return 0
    for문으로 i부터 i-(L-1)칸까지 i칸과 동일한지 확인한다.
  • 경사로 설치가 가능하다면 stmp라는 배열에 경사로를 체크해준다. --> 이렇게 안하면, 나중에 경사로 설치가 불가능해서 이 줄을 갈 수 없다고 판단될 때 smap에 이미 표시를 해준 걸 지워줘야 하기 때문에, 임시배열에 체크해뒀다가 이 줄이 갈 수 있다고 판단될 때 옮긴다. 

 

• i번째보다 i+1가 작을 경우,
  • 높이 차이 2 이상 ->갈 수 없음
  • i+1부터 뒤로 L칸, 즉, i+L칸까지 같아야 한다. 우선 i+L칸이 존재하는지 확인한다 -> 없으면 갈 수 없음
  • for문으로 i+1칸부터 i+L칸이 같은지 확인한다.
  • 경사로 설치가 가능하면 stmp에 경사로 체크해준다

 

다 확인할 때까지 return 0이 안되었으면 이 줄은 갈 수 있는 줄이란 것이다.

stmp에 있는 경사로 표시를 smap으로 최종적으로 옮겨준다

int Check_R(int r) {
	memset(stmp, 0, sizeof(stmp));
	// tmp에 있는 길 지나갈 수 있는지
	for (int i = 0; i < N-1; i++) {
		if (map[r][i] == map[r][i+1]) continue; // 같은 높이
		else if (map[r][i] < map[r][i+1]) { // 높아짐
			if (map[r][i + 1] - map[r][i] > 1) return 0; // 높이 차이가 2이상
			// i부터 역으로 L개가 같은 높이여야
			if (i - L + 1 < 0) return 0; 
			for (int j = 0; j < L; j++) {
				if (map[r][i] != map[r][i - j]) return 0; // L만큼 중에 다른 게 있음
				if (stmp[i - j] == 1) return 0;
			}
			// 아니면 괜찮음 => 경사로를 설치한다
			for (int j = 0; j < L; j++) {
				stmp[i - j] = 1;
			}
		}
		else { // 낮아짐
			if (map[r][i] - map[r][i+1] > 1) return 0; // 높이 차이가 2이상
			// i+1 부터 L개가 같은 높이여야
			if (i + L >= N) return 0;
			for (int j = 0; j < L; j++) {
				if (map[r][i+1] != map[r][i +1+ j]) return 0; // L만큼 중에 다른 게 있음
				if (stmp[i + j + 1] == 1) return 0;
			}
			// 아니면 괜찮음 => 경사로를 설치한다
			for (int j = 0; j < L; j++) {
				stmp[i + j+1] = 1;
			}
		}
	}
	// 경사로 붙이기
	for (int i = 0; i < N; i++) {
		if (stmp[i] == 1) {
			smap[r][i] = 1;
		}
	}
	return 1;
}

 

최종 코드

#include <stdio.h>
#include <string.h>
#define MAXN 100

int N, L;
int map[MAXN + 2][MAXN + 2];
int smap[MAXN + 2][MAXN + 2];
int stmp[MAXN + 2];
int tmp[MAXN + 2];
int cnt = 0;

void Get_Input(void) {
	scanf("%d %d", &N, &L);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
		}
	}
}

int Check_R(int r) {
	memset(stmp, 0, sizeof(stmp));
	// tmp에 있는 길 지나갈 수 있는지
	for (int i = 0; i < N-1; i++) {
		if (map[r][i] == map[r][i+1]) continue; // 같은 높이
		else if (map[r][i] < map[r][i+1]) { // 높아짐
			if (map[r][i + 1] - map[r][i] > 1) return 0; // 높이 차이가 2이상
			// i부터 역으로 L개가 같은 높이여야
			if (i - L + 1 < 0) return 0; 
			for (int j = 0; j < L; j++) {
				if (map[r][i] != map[r][i - j]) return 0; // L만큼 중에 다른 게 있음
				//if (smap[r][i - j] == 1) return 0;
				if (stmp[i - j] == 1) return 0;
			}
			// 아니면 괜찮음 => 경사로를 설치한다
			for (int j = 0; j < L; j++) {
				stmp[i - j] = 1;
			}
		}
		else { // 낮아짐
			if (map[r][i] - map[r][i+1] > 1) return 0; // 높이 차이가 2이상
			// i+1 부터 L개가 같은 높이여야
			if (i + L >= N) return 0;
			for (int j = 0; j < L; j++) {
				if (map[r][i+1] != map[r][i +1+ j]) return 0; // L만큼 중에 다른 게 있음
				//if (smap[r][i + j+1] == 1) return 0;
				if (stmp[i + j + 1] == 1) return 0;
			}
			// 아니면 괜찮음 => 경사로를 설치한다
			for (int j = 0; j < L; j++) {
				stmp[i + j+1] = 1;
			}
		}
	}
	// 경사로 붙이기
	for (int i = 0; i < N; i++) {
		if (stmp[i] == 1) {
			smap[r][i] = 1;
		}
	}
	return 1;
}


int Check_C(int c) {
	memset(stmp, 0, sizeof(stmp));
	// tmp에 있는 길 지나갈 수 있는지
	for (int i = 0; i < N - 1; i++) {
		if (map[i][c] == map[i+1][c]) continue; // 같은 높이
		else if (map[i][c] < map[i+1][c]) { // 높아짐
			if (map[i+1][c] - map[i][c] > 1) return 0; // 높이 차이가 2이상
			// i부터 역으로 L개가 같은 높이여야
			if (i - L + 1 < 0) return 0;
			for (int j = 0; j < L; j++) {
				if (map[i][c] != map[i-j][c]) return 0; // L만큼 중에 다른 게 있음
				//if (smap[i - j][c] == 1) return 0;
				if (stmp[i - j] == 1) return 0;
			}
			// 아니면 괜찮음 => 경사로를 설치한다
			for (int j = 0; j < L; j++) {
				stmp[i-j] = 1;
			}
		}
		else { // 낮아짐
			if (map[i][c] - map[i+1][c] > 1) return 0; // 높이 차이가 2이상
			// i+1부터 역으로 L개가 같은 높이여야
			if (i + L >= N) return 0;
			for (int j = 0; j < L; j++) {
				if (map[i+1][c] != map[i+1+j][c]) return 0; // L만큼 중에 다른 게 있음
				//if (smap[i +1+ j][c] == 1) return 0;
				if (stmp[i + 1 + j] == 1) return 0;
			}
			// 아니면 괜찮음 => 경사로를 설치한다
			for (int j = 0; j < L; j++) {
				stmp[i + j+1] = 1;
			}
		}
	}
	// 경사로 붙이기
	for (int i = 0; i < N; i++) {
		if (stmp[i] == 1) {
			smap[i][c]++;
		}
	}
	return 1;
}

void Solve(void) {
	for (int r = 0; r < N; r++) {
		cnt += Check_R(r);
	}
	for (int c = 0; c < N; c++) {
		cnt += Check_C(c);
	}
}

int main(void) {
	Get_Input();
	Solve();
	printf("%d", cnt);
	return 0;
}