[시뮬레이션] 금 채굴하기

문제링크

https://www.codetree.ai/missions/2/problems/gold-mining?&utm_source=clipboard&utm_medium=text

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

1. 핵심

• L1 거리는 구하는 방법

•  방법1. 같은 거리에 존재하는 마름모 껍질에 존재하는 좌표들 구하기

# 좌표(0, 0) 기준 거리가 k인 점들의 집합
def taxi_circle(k):
    if k == 0:
        return [(0, 0)]
    # 거리가 k라는 것은 x좌표 + y좌표 = k 가 됨을 의미한다.
    points = []
    # 축 - 양, 음
    points.append((k, 0))
    points.append((-k, 0))
    points.append((0, k))
    points.append((0, -k))
    # 1사분면 - 2사분면
    for i in range(1, k):
        points.append((i, k - i))
        points.append((i, -(k - i)))
    # 3 - 4 사분면
    for i in range(1, k):
        points.append((-i, k - i))
        points.append((-i, -(k - i)))

    return points

# k는 거리르 의미함. 최대 거리는 얼마가 될 수 있을까?
# n = 5  >> max_k = 8
max_k = 2 * (n - 1)

delta = []
for i in range(0, max_k + 1):
    delta.append(taxi_circle(i))

 

• 방법2. L1거리이므로 두 좌표의 차를 활용하기 - 좌표 (row, col) 을 기준으로 (i, j)에 대해서 L1 거리 구하는 공식을 통해서 k보다 작은 경우 모두 검토하기 

def get_num_of_gold(row, col, k):
    return sum([
        grid[i][j]
        for i in range(n)
        for j in range(n)
        if abs(row - i) + abs(col - j) <= k
    ])

2. 코드(Python)

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

dr = [-1, 1, 0, 0]
dc = [0 , 0, -1, 1]

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

# 좌표(0, 0) 기준 거리가 k인 점들의 집합
def taxi_circle(k):
    if k == 0:
        return [(0, 0)]
    # 거리가 k라는 것은 x좌표 + y좌표 = k 가 됨을 의미한다.
    points = []
    # 축 - 양, 음
    points.append((k, 0))
    points.append((-k, 0))
    points.append((0, k))
    points.append((0, -k))
    # 1사분면 - 2사분면
    for i in range(1, k):
        points.append((i, k - i))
        points.append((i, -(k - i)))
    # 3 - 4 사분면
    for i in range(1, k):
        points.append((-i, k - i))
        points.append((-i, -(k - i)))

    return points

# k는 거리르 의미함. 최대 거리는 얼마가 될 수 있을까?
# n = 5  >> max_k = 8
max_k = 2 * (n - 1)

delta = []
for i in range(0, max_k + 1):
    delta.append(taxi_circle(i))
    
ans = 0
for r in range(n):
    for c in range(n):
        gold_cnt = 0
        for k in range(0, max_k + 1):
            for dr, dc in delta[k]:
                nr = r + dr
                nc = c + dc
                if in_range(nr, nc) and board[nr][nc] == 1:
                    gold_cnt += 1
                if gold_cnt * m >= k * k + (k + 1) * (k + 1):
                    ans = max(ans, gold_cnt)

print(ans)