[알고리즘] 경사로 + 활주로 건설

포인트

• 가로 세로를 똑같은 함수를 이용하여 구한다. (사용되는 파라미터 배열 어떻게 들어가는지 볼 것)

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

#include<iostream>
#include<cmath>

#define endl "\n"
#define MAX 100
using namespace std;

int n, k;
int map[MAX][MAX];
int map2[MAX][MAX];


bool canMakeRoad(int A[][MAX], int x, int y) {
    int cmp = A[x][y + 1];
    for (int j = y + 1; j < y + 1 + k; j++) {
        if (A[x][j] != cmp) return false;
    }
    return true;
}

int make(int A[][MAX]) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        bool can = true;
        int before = 1;

        for (int j = 0; j < n - 1; j++) {
            if (A[i][j] == A[i][j + 1]) before++;    // 1번 Case
            else if (A[i][j] == A[i][j + 1] + 1) { // 2번 Case 앞에것이 더 높을 때
                if (canMakeRoad(A, i, j) == true) {
                    j = j + k - 1;
                    before = 0;
                } else {
                    can = false;
                    break;
                }
            } else if (A[i][j] + 1 == A[i][j + 1]) { // 3번 Case 뒤에것이 더 높을 때
                if (before >= k) {
                    before = 1;
                } else {
                    can = false;
                    break;
                }
            } else if (abs(A[i][j] - A[i][j + 1]) >= 2) {
                can = false;
                break;
            }
        }

        if (can) total++;
    }
    return total;
}

int main(void) {

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            map2[j][i] = map[i][j];
        }
    }

    int A = make(map);
    int B = make(map2);

    cout << A + B << endl;

    return 0;
}

python

import sys

input = sys.stdin.readline


def road(data: list, i: int) -> int:
	check = [0 for _ in range(n)]
	for j in range(n - 1):
		if abs(data[i][j] - data[i][j + 1]) > 1:
			# 1. 가로 이동 가능한지 검사한다
			# 2. 경사로를 배치했는지 검사하는 리스트 check를 만든다
			# 3. 이동할 때 다음 칸과의 차이가 1보다 크면 return한다
			return 0
		
		if data[i][j] < data[i][j + 1]:
			# 4. 오르막길일 경우 길이 l 만큼 오르막길을 배치할 수 있는지 확인한다
			temp = [0 for _ in range(n)]
			for k in range(l):
				if j - k < 0:
					return 0
				if data[i][j] != data[i][j - k] or check[j - k] != 0:
					return 0
				temp[j - k] = 1
			check = temp
		
		elif data[i][j] > data[i][j + 1]:
			temp = [0 for _ in range(n)]
			# 5. 내리막길일 경우 다음 칸 부터 시작해서 길이 l 만큼 내리막길을 배치할 수 있는지 확인한다
			for k in range(l):
				if j + k + 1 >= n:
					return 0
				if data[i][j + 1] != data[i][j + k + 1] or check[j + k + 1] != 0:
					return 0
				temp[j + k + 1] = 1
			check = temp
	return 1


# 6. 끝까지 도착하면 1을 return 경사로 개수를 증가시킨다


n, l = map(int, input().split())
data1 = [list(map(int, input().split())) for _ in range(n)]

data2 = []
for row in zip(*data1):
	data2.append(row)

answer = 0
for i in range(n):
	answer += road(data1, i)
	answer += road(data2, i)
print(answer)