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

문제

https://www.codetree.ai/trails/complete/curated-cards/challenge-gold-mining/description

Code Tree | Learning to Code with Confidence

해결방법

문제 지문을 요약하면 다음과 같다.

• 손해를 보지 않을때 K길이의 마름모 모양 안에 존재할 수 있는 금의 최대 개수
  • 채굴 비용 공식 K * K + (K + 1) * (K + 1)

K길이의 마름모 모양 안에 금이 존재하는지 판별하는 공식은 다음과 같다.

• 마름모 중앙과 금의 위치에 대한 맨하튼 거리가 K보다 작거나 같아야함. (|x1 - x2| + |y1 - y2| <= k)

 

문제에서 주어진 제약조건에 따르면 n은 최대 20이고, 시간제한은 1000ms이므로, 2차원 영역을 전체 순환하는 약O(n^6)까지 해결 가능하다. 그러므로 알고리즘을 다음과 같이 구현하여 문제를 해결할 수 있다.

• 2차원 반복문으로 0..n까지 순회
  • i, j위치에서 손해를 보지 않고 채굴할 수 있는 금의 최대 개수 계산

i, j위치에서 금의 최대 개수를 계산할때 사용할 수 있는 방법은 아래의 두가지 방법이 있다.

1. 2차원 반복문으로 배열 전체 순회하여 값이 1인 위치와 맨하튼 거리 계산
2. 금의 위치(x, y좌표)를 저장한 리스트를 순회하여 현재 위치(i, j)와 맨하튼 거리 계산

1번의 경우 구현난이도가 낮고, 시간복잡도가 O(n^5)으로 시간제한에 걸리지 않고 문제를 해결할 수 있다. 그러나 2번의 경우 2차 순회를 하지 않고, 1차원인 금의 위치 리스트만을 순회하므로 최악인 경우O(n^5)으로 1번의 경우보다 조금 더 개선된 시간복잡도를 가질 수 있다.

 

소스코드

import java.io.*;
import java.util.*;
   
   
class Position{
    int x;
    int y;
    Position(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static int manhattanDistance(int x1, int y1, int x2, int y2){
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }

    public static void main(String[] args) throws IOException {
        // Please write your code here.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        List<Position> golds = new ArrayList<>();

        for(int i = 0; i < n; i++){
            line = br.readLine().split(" ");
            for(int j = 0; j < n; j++){
                if(Integer.parseInt(line[j]) == 1){
                    Position goldPos = new Position(j, i);
                    golds.add(goldPos);
                }
            }
        }

        int answer = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                int k = 0;
                while(true){
                    int cnt = 0;
                    for(Position pos : golds){
                        if(manhattanDistance(j, i, pos.x, pos.y) <= k)
                            cnt++;
                    }

                    int dig_cost = k * k + (k + 1) * (k + 1);
                    int income = cnt * m;
                    if(income - dig_cost >= 0){
                        answer = answer > cnt ? answer : cnt;
                    }
                    k++;

                    if(cnt == golds.size())
                        break;
                }
            }
        }

        System.out.println(answer);
    }

}