파이썬(알고리즘) :: 봉우리 개수 찾기 (탐색 문제)

이번에는 탐색 문제 유형 중 하나인 봉우리 개수 찾는 문제에 대하여 정리를 해보려고 한다,

 

문제는 다음과 같다.

>  N*N 격자판이 주어지고, 각각의 격자에는 높이가 들어가 있다. 각 격자를 기준으로 상하좌우를 비교했을 때 가장 큰 높이가 봉우리일 때, 봉우리 개수를 구하라. (단 격자판의 가장자리는 모두 0으로 초기화 한다.)

 

 

# 접근 방법

 

위 그림과은 3*3 행렬이 주어진 후, 격자판 가장자리를 0으로 초기화 했을때의 그림이다.

 

2차원 배열을 탐색하는 문제이기 때문에 이중 for문으로 2차원 배열을 탐색한다.

배열의 각 요소를 탐색하면서 상하좌우로 크기 비교를 진행한다.

 

만약 matrix[i][j] 를 탐색한다고 했을때, matrix[i+1][j] matrix[i-1][j] matrix[i][j+1] matrix[i][j-1] 위치에 해당하는 요소랑 크기 비교를 한다.

 

 

# 풀이

def check_num(matrix):
    answer = 0
    size   = len(matrix)
    dx     = [-1, 0, 1, 0]
    dy     = [0, 1, 0, -1]

    matrix.append([0]*size)
    matrix.insert(0,[0]*size)

    # 양 끝에 0 추가
    for i in range(size+2):
        matrix[i].insert(0,0)
        matrix[i].append(0)
    
    # 비교 대상 숫지 기점으로 동서남북에 위치한 수랑 비교
    for i in range(1,size+1):
        for j in range(1,size+1):
            if all(matrix[i][j] > matrix[i+dx[k]][j+dy[k]] for k in range(4)):
                answer += 1

    return answer

matrix = [[3,3,7,2,3], [5,7,1,6,1], [7,2,5,3,4], [4,9,6,4,1], [8,7,3,5,2]]
print(check_num(matrix))

 

 

# 실행 결과

(base) Waveui-MacBookPro:coding_test wave$ python test.py 
9