Algorithm - 봉우리 찾기

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[봉우리 찾기]

 

지도의 정보가 N*N 격자판에 주어진다. 각 격자에는 그 지역의 높이가 쓰여있다.

각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역이며, 봉우리 지역이 몇 개 인지를 알아내는 프로그램을 작성하시오.

 

단, 격자의 가장자리는 0으로 초기화 되었다고 가정하며 만약 N=5이고 격자판의 숫자가 아래과 같다면 봉우리의 개수는 10개이다.

지도 정보

 

 

*입력 설명

첫 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 50)

두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. (단, 각 자연수는 100을 넘지 않음)

 

*출력 설명

봉우리의 개수를 구하시오.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_19.txt', 'rt')

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

a.insert(0, [0] * n)
a.append([0] * n)
for x in a:
    x.insert(0, 0)
    x.append(0)

cnt = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        if all(a[i][j] > a[i + dx[k]][j + dy[k]] for k in range(4)):
            cnt += 1
print(cnt)

 

input_19.txt(입력)

5
5 3 7 2 3
3 7 1 6 1 
7 2 5 3 4 
4 3 6 4 1 
8 7 3 5 2

 

 

중요내용

1. append() 함수는 인자로 받은 데이터를 해당 리스트의 맨 마지막 부분에 추가한다.
2. insert() 함수, append() 함수와 for문을 사용하여, 입력받은 데이터의 가장자리를 0으로 설정한다. (중요)
3. a[i][j] > a[i + dx[k][j + dy[k]] for k in range(4) 코드는 리스트 a의 a[i][j]를 기준으로 상하좌우를 탐색하는 코드이다.
4. 상하좌우로 탐색하는 코드를 만들기에 앞서, dx = [-1, 0, 1, 0]와 dy = [0, 1, 0, -1] 코드를 사용하여 초기 설정을 해야한다.
5. all() 함수는 인자로 들어온 값이 모두 참(True)일 때, 참(True)를 반환한다.