[코드트리] 완전탐색 - 금 채굴하기

코드트리 네이버 커리큘럼 - 완전탐색

• 금 채굴하기 (Python)
  https://www.codetree.ai/cote/14/problems/gold-mining/description

Code

from collections import deque

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

def check_range(x, y):
    if(x < 0 or y < 0 or x >= n or y >= n):
        return False
    return True

def get_gold(arr):
    cnt_gold = 0
    for i in range(len(arr)):
        loc = arr[i]
        if (matrix[loc[0]][loc[1]] == 1):
            cnt_gold += 1
    return cnt_gold

# k번 이내로 인접한 곳으로 이동 가능한 BFS
def bfs(q, visited, curr_k):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    while (q):
        curr = q.popleft()
        x = curr[0]
        y = curr[1]
        k = curr[2]

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if (check_range(nx, ny) and visited[nx][ny] == 0 and k+1 <= curr_k):
                q.append((nx, ny, k+1))
                visited[nx][ny] = 1
                bfs_list.append((nx, ny, k+1))
    return bfs_list

## main
k = 0
bfs_list = []

q = deque()

curr_k = 0
max_gold = 0
answer = 0

for i in range(n):
    for j in range(n):
        for kk in range(n+1):
            curr_k = kk

            visited = [list(0 for _ in range(n)) for _ in range(n)]
            center = (i, j, k)
            visited[i][j] = 1

            bfs_list = []
            bfs_list.append(center)

            q.append(center)

            bfs_list = bfs(q, visited, curr_k)

            cost = (curr_k * curr_k + (curr_k + 1) * (curr_k + 1))      # 비용
            earn = get_gold(bfs_list)       # 수익

            # 손해가 없다면 -> 최댓값을 정답으로
            if (cost <= earn * m):
                answer = max(answer, earn)

print(answer)

풀이 및 해설

• 고려해야 할 부분
  • 영역이 벗어나도 손해가 없다면 금 채굴 가능한 것으로 판정
  • 최댓값을 구하는 과정에서 k=0 일때만 최대값일 때
• BFS로 k 만큼 이동 가능한 인접한 좌표들을 모두 bfs_list에 담는다 → 해당 리스트에서 드는 비용, 수익을 구한다 → 손해가 나지 않는다면 해당 좌표들에서 채굴 가능한 금의 개수를 기존 최댓값과 비교하여 answer를 업데이트 해준다.

What I learned

BFS로 번거롭게 구하지 않아도 되었던 문제 !

→ k에 대한 공식이 주어져서 이를 활용하면 마름모의 넓이를 구할 수 있음 → 이 넓이를 가지고 각 위치가 마름모의 중앙일 때 채굴 가능한 금의 개수를 구하기

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

# 주어진 k에 대하여 마름모의 넓이를 반환합니다.
def get_area(k):
    return k * k + (k + 1) * (k + 1)

# 주어진 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
    ])

max_gold = 0

# 격자의 각 위치가 마름모의 중앙일 때 채굴 가능한 금의 개수를 구합니다.
for row in range(n):
    for col in range(n):
        for k in range(2 * (n - 1) + 1):
            num_of_gold = get_num_of_gold(row, col, k)
            
            # 손해를 보지 않으면서 채굴할 수 있는 최대 금의 개수를 저장합니다.
            if num_of_gold * m >= get_area(k):
                max_gold = max(max_gold, num_of_gold)

print(max_gold)