[시물레이션] -웅덩이

웅덩이

매개변수 nums에 n행 n열의 이차원 배열에 격자판 정보가 주어집니다.
각 격자에는 그 지역의 높이가 쓰여있습니다. 각 지역은 상하좌우 인접한 지역의 숫자가 모두 자신보다 클 경우 이 지역을 웅덩이 지역이라고 합니다.
격자의 가장자리는 1000으로 초기화 되었다고 가정한다.
만약 5*5 이차원 배열의 격자판 정보가아래와 같다면 총 웅덩이의 수는 5개입니다.

 

주어진 격자에 웅덩이가 몇 개 있는지 찾아 그 개수를 반환하는 프로그램을 작성하세요.

 

제한사항:
• 3 <= n <= 10
• 배열 nums의 원소는 자연수입니다. 1 <= nums[i][j] <= 100

 

나의 코드 

def solution(nums):
    n=len(nums)
    nums.insert(0,[1000]*(len(nums)))
    nums.append([1000]*(len(nums)-1))
    for x in nums:
        x.insert(0,1000)
        x.append(1000)

    answer = 0
    dx=[-1,0,1,0]
    dy=[0,1,0,-1]
    for i in range(1,n+1):
        for j in range(1,n+1):
            flag=0
            for k in range(4):
                nx=i+dx[k]
                ny=j+dy[k]
                if  nums[i][j]>=nums[nx][ny]:
                    flag=1
                    break
            if flag==0:
              
                answer+=1


    

    return answer
                       
print(solution([[10, 20, 50, 30, 20], [20, 30, 50, 70, 90], [10, 15, 25, 80, 35], [25, 35, 40, 55, 80], [30, 20, 35, 40, 90]]))
print(solution([[80, 25, 10, 65, 100], [20, 10, 32, 70, 33], [45, 10, 88, 9, 90], [10, 35, 10, 55, 66], [10, 84, 65, 88, 99]]))
print(solution([[33, 22, 55, 65, 55], [55, 88, 99, 12, 19], [18, 33, 25, 57, 77], [46, 78, 54, 55, 99], [33, 25, 47, 85, 17]]))

 

처음 방향 벡터를 만들고 탐색하는것까지는 바로 생각을 했지만 flag를 안쓰고 로직을 작성하려다가 시간을 쬐끔 소비했다.

그리고 2번째 입력값에서 정답보다 4가 많이 나와서 해당 입력에 대해 그림을 그려 파악해보니 해당 탐색 지점보다 같은 경우 는 고려하지 않아서 같은 지점들 까지 카운팅이 되어서 그랬다. 그래도 그림을 그려 빠르게 문제를 찾아서 다행이다.

아래는 해당 반례에 대한 그림이다.

 

 

 

 

정답 코드

def solution(nums):
    answer = 0
    n = len(nums)
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    for i in range(n):
        for j in range(n):
            flag = True
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]
                if nx >= 0 and nx < n and ny >= 0 and ny < n and nums[i][j] >= nums[nx][ny]:
                    flag = False
                    break
            if flag == True:
                answer += 1

    return answer
                       
print(solution([[10, 20, 50, 30, 20], [20, 30, 50, 70, 90], [10, 15, 25, 80, 35], [25, 35, 40, 55, 80], [30, 20, 35, 40, 90]]))
print(solution([[80, 25, 10, 65, 100], [20, 10, 32, 70, 33], [45, 10, 88, 9, 90], [10, 35, 10, 55, 66], [10, 84, 65, 88, 99]]))
print(solution([[33, 22, 55, 65, 55], [55, 88, 99, 12, 19], [18, 33, 25, 57, 77], [46, 78, 54, 55, 99], [33, 25, 47, 85, 17]]))

나와 거의 비슷하지만 초기 입력값의 테두리 값을 1000으로 하지 않고 작성 하였다.

nx >= 0 and nx < n and ny >= 0 and ny < n이 그역활을 대신해서 초기 세팅없이 깔끔하게 작성이 된것같다.