[코드트리] [학습하기] [시뮬레이션] 금 채굴하기

https://www.codetree.ai/missions/2/problems/gold-mining/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제 

n×n크기의 이차원 영역에 파묻힌 금을 손해를 보지 않는 선에서 최대한 많이 채굴하려고 합니다. 채굴은 반드시 [그림 1, 2]과 같은 마름모 모양으로 단 한 번 할 수 있으며, 마름모 모양을 지키는 한 [그림 3]와 같이 이차원 영역을 벗어난 채굴도 가능하지만 이차원 영역 밖에 금은 존재하지 않습니다.

여기서 마름모 모양이란 특정 중심점을 기준으로 K번 이내로 상하좌우의 인접한 곳으로 이동하는 걸 반복했을 때 갈 수 있는 모든 영역이 색칠되어 있는 모양을 의미합니다. [그림 1]은 K가 1일때의 마름모 모양이고, [그림 2]는 K가 2일때 마름모 모양입니다. K가 0인 경우는 지점 한 곳에서만 채굴하는 것을 의미하며 이 역시 올바른 마름모 모양이라 할 수 있습니다. 올바르지 않은 마름모 모양을 이용해서는 채굴이 불가능합니다.

이 때 채굴에 드는 비용은 마름모 안의 격자 갯수만큼 들어가며, 이는 K∗K+(K+1)∗(K+1)로 계산될 수 있습니다. 금 한 개의 가격이 m일 때, 손해를 보지 않으면서 채굴할 수 있는 가장 많은 금의 개수를 출력하는 코드를 작성해보세요. 단 한 개의 격자 안에는 최대 한 개의 금만 존재합니다

 

입력형식

첫 번째 줄에는 n과 m이 공백을 사이에 두고 주어지고,

두 번째 줄부터 (n+1)번째 줄까지는 각 행에 금이 있는 경우 1, 없는 경우 0으로 입력이 공백을 사이에 두고 주어집니다.

• 1≤n≤20
• 1≤m≤10

출력형식 

손해를 보지 않으면서 채굴할 수 있는 가장 많은 금의 개수를 출력해줍니다.

 

입출력예제 

예제 1 

입력:

5 5
0 0 0 0 0
0 1 0 0 0
0 0 1 0 1
0 0 0 0 0
0 0 0 1 0

 

출력:

3

---

내가 푼 방식 

마름모를 다 확인하는데 '맨위에서 중간으로'와 '맨아래에서 중간으로'가 동시에 작동하고 마지막에 중간만 따로 확인해준다. 

import sys

def in_range(r,c):
    return 0<=r<n and 0<=c<n

def filter(x,y):
    ans=0
    for k in range(max_k):
        cost = k**2+(k+1)**2
        profit=0
        cnt=0
        for i in range(k):
            for j in range(y-i,y+i+1):
                if in_range(x-(k-i),j) and board[x-(k-i)][j]==1:
                    cnt+=1
                if in_range(x+(k-i),j) and board[x+(k-i)][j]==1:
                    cnt+=1
                    
        # 마름모 가운데
        for l in range(y-k,y+k+1):
            if in_range(x,l) and board[x][l]==1:
                cnt += 1
                
        profit = cnt*m
        profit -= cost
        
        if profit>=0:
            ans = max(ans, cnt)


    return ans

if __name__=="__main__":
    n,m=map(int, input().split())   # nxn,  m:금 하나의 가격 
    board = [list(map(int, input().split())) for _ in range(n)]
    
    # n이 3일때, k는 최대 2
    # n이 5일때, k는 최대 4
    max_k=n+1
    answer = 0
    
    for i in range(n):
        for j in range(n):
            tmp=filter(i,j)
            answer = max(answer,tmp)
            
    print(answer)

 

---

해설 중 하나의 코드 

중복되는 경우 제외하여 효율적으로 탐색하기 

K범위에 대하여 모두 탐색할 때 매번 새로 마름모를 탐색하였다. 그러나 잘 생각해보면 K=a일때, 내부에 있는 금의 개수는 (K=a-1일 때 금의 개수) + (K=a일때 그려지는 마름모의 가장자리에 있는 금의 개수)로 구할 수 있다. 이러한 특성을 활용하여 보다 효율적으로 탐색할 수 있다. 

 

아래 그림과 같이 k=2일 때, 아래 그림과 같이 k=1일 때와 k=2일 때의 가장자리의 합으로 구할 수 있다. 따라서 가능한 k범위인 0~2*(n-1)에 대해서 탐색을 할 때 매번 새로 마름모 안의 영역을 탐색하는 것이 아니라 이전에 탐색했던 마름모 내부의 금 개수에 해당 마름모의 모서리에 있는 금의 개수만 더해주면 된다. 

 

import sys
sys.stdin=open('input.txt', 'r')


def get_area(k):
    return k * k + (k + 1) * (k + 1)


def in_range(x, y):
    return 0 <= x and x < n and 0 <= y and y < n


# 주어진 k에 대하여 채굴 가능한 금의 개수를 반환합니다.
def get_num_of_gold_in_border(row, col, k):
    # 방향에 따라 바뀌는 x와 y의 변화량을 정의합니다.
    dxs = [1, 1, -1, -1]
    dys = [-1, 1, 1, -1]
    
    if k == 0:
        return grid[row][col]
    
    # 겉에 부분만 핥기 
    num_of_gold = 0
    curr_x, curr_y = row - k, col # 순회 시작점 설정
    for dx, dy in zip(dxs, dys):
        for _ in range(k):
            if in_range(curr_x, curr_y):
                num_of_gold += grid[curr_x][curr_y]

            curr_x = curr_x + dx
            curr_y = curr_y + dy
    
    return num_of_gold


if __name__=="__main__":
    # 변수 선언 및 입력
    n, m = tuple(map(int, input().split()))
    grid = [list(map(int, input().split())) for _ in range(n)]

    max_gold = 0

    for row in range(n):
        for col in range(n):
            num_of_gold = 0
            for k in range(2 * (n - 1) + 1):        # k=0, k=1, k=2
                # 이전 k까지 구한 금의 개수에
                # 해당 k의 모서리에 존재하는 금의 개수를 더해줍니다.
                num_of_gold += get_num_of_gold_in_border(row, col, k)
                
                # 손해를 보지 않으면서 채굴할 수 있는 최대 금의 개수를 저장합니다.
                if num_of_gold * m >= get_area(k):
                    max_gold = max(max_gold, num_of_gold)

    print(max_gold)