[Algorithm][C++] SWEA. 4014. [모의 SW 역량테스트] 활주로 건설

url: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH 

SW Expert Academy

 

풀이 핵심

1. 높이 차이가 2 이상 나는지 확인해주기, 내리막길 + 오르막길 일 경우 경사로가 중복인지 확인하기

이 두가지만 잘 확인해준다면 쉽게 풀 수 있다.

 

2. 행/열을 각각 체크해주려면 경사로 중복 배열을 행 체크 후 다시 초기화시켜줘야 하므로 행 체크만 할 수 있도록 입력에서 처리해준다. (따라서 행을 2 * N번 체크해줘야 함)

...
scanf("%d", &map[r][c]);
map[N + c][r] = map[r][c];
...

 

3. line_pass, point_pass 두 가지 pass 조건을 확인하며 각 행을 체크한다.

- 높이가 다른 곳을 만나면 높이차이가 1인지 확인한다. 그렇지 않으면 line_pass를 false로 변경하고 행 체크를 종료한다.

 

- 높이차이가 1이라면 체크해야 하는 위치, 방향(오르막길, 내리막길)을 확인한다.

 

- 만약 오르막길이라면 체크해야하는 위치에 경사로가 놓여있는지 확인한다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#define MAXN	20

int T, N, X;
int map[2 * MAXN][MAXN];
bool check[2 * MAXN][MAXN];

int get_abs(int value) {
	return value > 0 ? value : -value;
}

int solve() {
	int ret = 0;
	for (int r = 0; r < 2 * N; r++) {
		bool line_pass = true;
		int cur = map[r][0];
		int c = 1;
		while (1) {
			if (c == N) {
				break;
			}
			if (cur != map[r][c]) {
				if (get_abs(cur - map[r][c]) != 1) {
					line_pass = false;
					break;
				}
				bool point_pass = false;
				int cnt = 1;
				int target, target_idx, dc;
				if (cur > map[r][c]) {
					target = map[r][c];
					target_idx = c + 1;
					dc = +1;
				}
				else {
					if (check[r][c - 1]) {
						line_pass = false;
						break;
					}
					target = cur;
					target_idx = c - 2;
					dc = -1;
				}
				while (1) {
					if (cnt == X) {
						point_pass = true;
						if (dc == 1) {
							cur = target;
							c = target_idx;
							check[r][target_idx - 1] = true;
						}
						else {
							cur = map[r][c];
							c++;
						}
						break;
					}
					if (target_idx < 0 || target_idx >= N || \
						target != map[r][target_idx] || check[r][target_idx]) {
						break;
					}
					cnt++;
					target_idx += dc;
				}
				if (!point_pass) {
					line_pass = false;
					break;
				}
			}
			else {
				c++;
			}
		}
		if (line_pass) {
			ret++;
		}
	}

	return ret;
}

int main() {
	// freopen("input.txt", "r", stdin);
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		scanf("%d %d", &N, &X);
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				scanf("%d", &map[r][c]);
				check[r][c] = check[N + c][r] = 0;
				map[N + c][r] = map[r][c];
			}
		}

		int ans = solve();
		printf("#%d %d\n", tc, ans);
	}
	return 0;
}

 

조건을 깔끔하게 만들지 못해 아쉽다. 남이 이해하기에는 조금 시간이 걸릴 좋지 않은 코드라고 생각한다.