[탐색 및 시뮬레이션] 파이썬 알고리즘 문제 2-9 "봉우리"

봉우리

 

[시간복잡도]

O(N²) : 이중 for문을 통해서 2차원 배열을 돌기 때문에 

[공간복잡도]

O(N²) : 2차원 배열을 사용해서 변수들을 저장하기 때문에

 

 

Problem

 

지도 정보가 N*N 격자판에 주어집니다.

각 격자에는 그 지역의 높이가 쓰여있습니다.

각 격자 판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요.

격자의 가장자리는 0으로 초기화 되었다고 가정한다.

만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다.

 

▣ 입력설명

 

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

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

 

▣ 출력설명

 

봉우리의 개수를 출력하세요.

 

▣ 입력예제

 

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

 

▣ 출력예제

 

10

 

 

💯 Solution ①

 

import sys
sys.stdin=open("input.txt","rt")
 
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
 
m=[[0]*(n+2) for _ in range(n+2)]
# [0] 값을 가장자리에 모두 둘렀음
for x in range(n):
    for y in range(n):
        if x<n+2 and y<n+2:
            m[x+1][y+1]=a[x][y]
 
res=0
 
# 상하좌우 비교하는 로직
for x in range(n+2):
    for y in range(n+2):
        if 0<x<n+1 and 0<y<n+1:
            # 자기자신을 제외한 max_num
            max_num=max(m[x][y-1],m[x][y+1],m[x-1][y],m[x+1][y])
            # 자기 자신이 상하좌우 값의 최댓값보다 크다면
            if m[x][y]>max_num:
                res+=1
 
print(res)

- 2차원 배열로 이루어진 배열에 주위에 [0]으로 가장자리를 채워야한다.

 

ex) 위의 입력값을 예시로 들어서 작성해보았다.

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

이를 위해서, 주어진 값(n)의 +2이며 [0]으로 이루어진 2차원 리스트(m)를 만든다.

 

m=[[0]*(n+2) for _ in range(n+2)]

 

m

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

그리고 임의로 만든 이 배열(m)에 주어진 배열(a)을 그대로 넣는다.

 

# [0] 값을 가장자리에 모두 둘렀음
for x in range(n):
    for y in range(n):
        if x<n+2 and y<n+2:
            m[x+1][y+1]=a[x][y]

이중 for문을 통해서 각 2차원 배열의 값들에 접근하고 해당 값들을 a[x][y] 값으로 대입하면, 내가 만들고 싶은 가장자리를 [0]으로 두른 배열을 만들 수 있게 되었다.

 

그리고 이제 상하좌우를 비교해서 자기 자신의 값이 제일 큰 지를 판단하는 로직의 코드를 작성하면 된다.

 

res=0
 
# 상하좌우 비교하는 로직
for x in range(n+2):
    for y in range(n+2):
        if 0<x<n+1 and 0<y<n+1:
            # 자기자신을 제외한 max_num
            max_num=max(m[x][y-1],m[x][y+1],m[x-1][y],m[x+1][y])
            # 자기 자신이 상하좌우 값의 최댓값보다 크다면
            if m[x][y]>max_num:
                res+=1
 
print(res)

res 라는 값을 0으로 두고. 이중 for문을 통해서 자신의 상하좌우 값들의 최댓값을 구한다. (자신은 제외한)

 

이렇게 구한 상하좌우들의 최댓값 (max_num)을 자기자신 m[x][y] 와 비교해서 자신이 더 크다면 봉우리에 해당하기 때문에, res +=1 을 해주고 res를 출력해주면 해당 2차원 배열의 봉우리의 갯수를 파악할 수 있다.

 

 

 

 

💯 Solution ②

 

# Tutor's Code
import sys
sys.stdin=open("input.txt", "r")
# (i,j)로 이루어진 2차원 배열에서 (i-1,j) = 왼쪽 값, (i,j+1) = 아래쪽 값, (i+1,j) = 오른쪽 값, (i,j-1) = 위쪽 값 
dx=[-1,0,1,0]
dy=[0,1,0,-1]
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
# 0번 행에 [0]으로 이루어진 n개의 리스트를 넣는다.
a.insert(0,[0]*n)
# 맨 마지막 행에 [0]으로 이루어진 n개의 리스트를 넣는다.
a.append([0]*n)
for x in a:
    # 제일 앞에다가 0을 넣어주기
    x.insert(0,0)
    # 제일 뒤에다가 0을 넣어주기
    x.append(0)
cnt=0
# 제일 처음은 돌지 않아도 됨
for i in range(1, n+1):
    for j in range(1, n+1):
        # i+dx[k] : 행 / j+dy[k] : 열
        # 이 조건이 모두 참이여야 if문을 탈 수 있음 (해당 조건을 4번 하는 것)
        if all(a[i][j]>a[i+dx[k][j+dy[k]] for k in range(4)):
            cnt+=1
            
print(cnt)
 
 

- 튜터님의 코드는 조금더 심플한 편이다.

- 우선 가장자리에 [0]을 두르기 위해서, append() 와 insert()를 사용해서 가장자리에 0을 채워넣었다.

 

a=[list(map(int,input().split())) for _ in range(n)]
# 0번 행에 [0]으로 이루어진 n개의 리스트를 넣는다.
a.insert(0,[0]*n)
# 맨 마지막 행에 [0]으로 이루어진 n개의 리스트를 넣는다.
a.append([0]*n)
for x in a:
    # 제일 앞에다가 0을 넣어주기
    x.insert(0,0)
    # 제일 뒤에다가 0을 넣어주기
    x.append(0)

 

이렇게 가장자리에 0을 둘렀다면, 이제는 상하좌우를 비교하는 코드를 작성해야한다.

 

# (i,j)로 이루어진 2차원 배열에서 (i-1,j) = 왼쪽 값, (i,j+1) = 아래쪽 값, (i+1,j) = 오른쪽 값, (i,j-1) = 위쪽 값 
dx=[-1,0,1,0]
dy=[0,1,0,-1]
 
...
 
cnt=0
# 제일 처음은 돌지 않아도 됨
for i in range(1, n+1):
    for j in range(1, n+1):
        # i+dx[k] : 행 / j+dy[k] : 열
        # 이 조건이 모두 참이여야 if문을 탈 수 있음 (해당 조건을 4번 하는 것)
        if all(a[i][j]>a[i+dx[k][j+dy[k]] for k in range(4)):
            cnt+=1
            
print(cnt)

 

상하좌우를 비교하는 코드에서 많이 작성한다고 하는데

 

dx=[-1,0,1,0]

dy=[0,1,0,-1]

 

이라는 리스트를 담은 변수 두 개를 만들고

이중 for문을 돌린다. (0번째 행과 열은 무시해야하기 때문에, range(1,n+1)로 작성한다.)

 

if 문과 all() 을 통해서 해당 조건이 모두 참이여야 cnt 값을 +1 하는 형식의 코드를 작성한다.

 

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

 

2차원 배열을 하나씩 꺼내서 비교하는데, [i] 와 [j] 값에 dx와 dy의 값들을 하나씩 꺼내서 더하고 뺀 인덱스를 가져오면서, 기준이 되는 a[i][j]의 상하좌우 값을 모두 비교하고 제일 큰 값이 a[i][j]인지 파악한다.

 

 

 

 

 

📚 참고

 

minjoos.tistory.com/2

[python] 2차원 리스트 생성 및 입력 받기, 원하는 값 찾기, 탐색, 전치 행렬

 

2차원 리스트의 한 좌표에서 인접 리스트 요소(상하좌우 값)를 탐색하고 싶을 때 사용하는 방법은 다음과 같다.

dx=[0,0,-1,1] #상하좌우
dy=[-1,1,0,0]
#델타 값을 이용하여 특정 원소의 상하좌우에 위치한 원소에 접근할 수 있음

for x in range(len(arr)):
    for y in range(len(arr[x])):
        for i in range(4):
            testX=x+dx[i]
            testY=y+dy[i]
            print(arr[testX][testY])

델타 값(dx, dy)은 한 좌표에서 네 방향의 좌표와 x, y의 차이를 저장한 리스트이다.

델타 값을 이용하여 특정 원소의 상하좌우에 위치한 원소에 접근할 수 있다.

 

    ** 2차원 리스트의 가장자리 원소들은 상하좌우 네 방향에 원소가 존재하지 않을 경우가 있으므로, 

        Index를 체크하거나 Index의 범위를 제한해야 한다.

 

 

 

 

⚙️저장소

github.com/JiHoon-JK/Algorithm/blob/main/inflearn/python/%EC%84%B9%EC%85%983-9.py

JiHoon-JK/Algorithm