[알고리즘 문제] 지형 조사 (Python / 파이썬)

문제

등산로를 조성하기 앞서 산의 지형 정보를 통해 오르막 및 내리막 구간 정보를 정리하려고한다. 이때 기록하게되는 오르막 이나 내리막 구간은 길이 K 이상 이면서, 높이가 2이상 차이나야한다. 예를 들어, 1 2 3 은 길이가 3인 오르막 구간이고, 4 5 6 7 8 은 길이가 5인 오르막 구간이다. 앞서 나온 오르막 구간들은 모두 높이가 1씩 차이나므로 기록해야되는 오르막 구간이 아니다. 2 5 8 은 높이차가 1씩 차이나지 않기 때문에 기록 대상인 오르막 구간이다.
주어진 지형의 가로 또는 세로 한 줄을 봤을때, 오르막이나 내리막 구간이 존재하는지 확인해야한다. N * N의 지형 정보가 주어졌을때, 몇 개의 가로 및 세로 줄에 오르막 혹은 내리막 구간이 몇 개 존재하는지 구해보자.
예를 들어, N 이 7인 지형 정보는 다음과 같이 주어진다.

이때, 조사 대상의 구간 길이가 3일 경우 마지막 가로줄에서 9, 6, 3 의 내리막 구간과 3, 5, 9 의 오르막 구간이 확인되므로 해당 가로줄은 기록 대상이다. 4번째 세로줄 또한 8, 4, 2 의 내리막 구간이 확인되므로 기록 대상이다.
기록 대상의 가로 및 세로 줄을 체크하면 총 5줄로 다음과 같다. 구간의 개수가 아닌 가로 및 세로 줄의 개수를 세어주는 것에 유의하자. 예를 들어, 앞서 살펴본 마지막 가로줄에서 2개의 구간이 있지만 현재 관심있는 정보는 가로 및 세로 줄이기 때문에 가로 줄 1개를 센다.

입력

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다. 다음 줄부터 T개의 테스트 케이스에 대한 정보가 주어진다. 각각의 테스트 케이스의 첫 번째 줄에 지형의 크기 N 과 구간 길이 K 가 공백을 통해 구분하여 주어진다. 두 번째 줄부터 N 개의 줄에 걸쳐 지형 정보가 주어진다. 한 줄에 N개의 숫자가 공백을 통해 주어진다. 지형 정보는 1이상 9이하이다. (5 ≤ N ≤ 100, 3 ≤ K ≤ 5)

출력

각 테스트 케이스에 대해 몇 개의 가로 및 세로 줄이 기록 대상인지 출력한다. 각 테스트 케이스의 출력 양식은 "#t r"이다. t는 테스트 케이스의 번호이며, 1부터 시작한다. r은 문제에 대한 결과값을 뜻한다.

---

문제 풀이

지형 조사 문제는 각 행과 열에서 길이가 k 이상이고 높이가 2 이상 차이나는

오르막 혹은 내리막길이 있는지 확인하는 문제이다. 

 

따라서 각 행과 열을 탐색하면서 오르막 혹은 내리막길이 있는지 탐색해주었다. 

이때 주의할 점은 오르막 내리막길의 개수를 세는 것이 아니라 

오르막 내리막길이 존재하는 행과 열의 개수를 세는 것이다. 

 

길이가 k 이상이고 높이가 2 이상 차이나는 오르막 내리막을 찾기 위해 

먼저 각 행에서 앞에서부터 이동해가며 k만큼 원소를 배열에 저장해주었다.

그런 다음 k개의 원소가 저장된 배열이 오르막 혹은 내리막인지, 높이가 2이상 차이나는지 확인해주었다. 

각 열에서도 동일한 방법을 이용해 탐색해주었다. 

만약 오르막 내리막이 있다면 해당 행 또는 열은 더 탐색할 필요가 없으므로 종료 후 

다음 행, 열로 넘어가 주었다. 

 

k개의 원소가 저장된 배열이 오르막 혹은 내리막인지, 높이가 2 이상 차이나는지 확인하기 위해

첫번째 원소와 두번째 원소의 차를 구해주었다. 

만약 음수라면 오르막이라는 것이고, 양수라면 내리막이라는 것이다. 

그런 다음 뒤의 원소들의 차를 구하며 만약 오르막인데 양수가 나오면 False 

내리막인데 음수가 나오면 False 를 반환하도록 해주었다. 

그리고 두 원소를 비교하며 차를 구하고 그 절댓값이 2보다 작다면 False 를 반환해주었다. 

만약 이 과정을 모두 통과 했다면 오르막 내리막에 해당하므로 True를 반환해주었다. 

---

My Code

# 오르막 내리막인지 확인하는 함수 
def check(arr):
    # 첫번째 두번째 원소의 차를 통해 오르막인지 내리막인지 저장 
    if arr[0] - arr[1] < 0: # 차가 음수면 
        check = True        # 오르막 
    else:                   # 차가 양수면
        check = False       # 내리막

    for i in range(k - 1):
        if abs(arr[i] - arr[i + 1]) < 2: # 두 수의 차의 절대값이 2보다 작으면
            return False                 # False 반환
        if check and arr[i] - arr[i + 1] > 0: # 오르막인데 양수가 나오면
            return False                 # False 반환
        if not check and arr[i] - arr[i + 1] < 0: # 내리막인데 음수가 나오면
            return False                 # False 반환
    return True # 아무것도 해당되지 않으면 True

for tc in range(int(input())):
    n, k = map(int,input().split()) # 지형의 크기, 구간 길이

    array = []
    for _ in range(n):
        array.append(list(map(int,input().split()))) # 지형 높이 정보 

    result = 0
    for i in range(n):
        # 각 행에서 탐색 
        for j in range(n - k + 1):
            new = []
            for p in range(k): # k개 만큼 배열에 넣어줌
                new.append(array[i][j + p])
            if check(new): # 오르막 내리막이라면 
                result += 1 # 개수를 세어주고 
                break       # 종료 후 다음 행으로 넘어감
        
        # 각 열에서 탐색
        for j in range(n - k + 1):
            new = []
            for p in range(k): # k개 만큼 배열에 넣어줌
                new.append(array[j + p][i])
            if check(new): # 오르막 내리막이라면
                result += 1 # 개수를 세어주고 
                break       # 종료 후 다음 열로 넘어감

    print('#' + str(tc + 1), end = ' ')
    print(result)