[코드트리 챌린지] 금 채굴하기

문제 설명 링크 : https://www.codetree.ai/missions/2/problems/gold-mining?&utm_source=clipboard&utm_medium=text

 

이번 문제는 완전탐색의 문제이다. 이 문제를 살펴보고 나서 처음 떠오른 건 코드를 시작한 지 얼마 안됐을때 접한 다이아몬드 그리기 문제였다. 당시엔 정말 어려웠는데... 지금도 이 문제가 물론 어려웠지만 수식을 짜고 코드로 구현한 결과 문제를 풀 수 있었다. k의 최대 크기는 한 변의 길이보다 1 작다고 가정하고 풀었다. 

import java.util.*;
import java.io.*;

public class Main {
    static int[][] arr2d;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] NM = br.readLine().split(" ");
        int N = Integer.parseInt(NM[0]);
        int M = Integer.parseInt(NM[1]);
        arr2d = new int[N][N];

        for(int i = 0; i < N; i++){
            String[] temp = br.readLine().split(" ");
            for(int j = 0; j < N; j++){
                arr2d[i][j] = Integer.parseInt(temp[j]);
            }
        }

        int max = 0;
        for(int k = 0; k < N; k++){
            for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                    int gold = shapeDiamond(N, k, M, i, j);
                    if(gold != -1){
                        max = (max < gold) ? gold : max;
                    }
                }
            }
            
        }

        System.out.print(max);
    }

    public static int cost(int k){
        return (k*k + (k+1)*(k+1));
    }

    public static int shapeDiamond(int N, int k, int m, int r, int c){
        int countOfGold = 0;
        for(int i = k*(-1); i < (k + 1); i++){
            if(i <= 0){
                int temp = (-k) - i;
                for(int j = temp; j < (-temp) + 1; j++){
                    if(r+i < 0 || r+i >= N || c+j < 0 || c+j >= N) continue;
                    if(arr2d[r + i][c + j] == 1) countOfGold += 1;
                }
            }
            else{
                int temp = k - i;
                for(int j = (-temp); j < temp + 1; j++){
                    if(r+i < 0 || r+i >= N || c+j < 0 || c+j >= N) continue;
                    if(arr2d[r + i][c + j] == 1) countOfGold += 1;
                }
            }
        }
        return (cost(k) <= countOfGold * m) ? countOfGold : -1;
    }
}