[PCCP 기출문제] 2번 / 석유 시추

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/250136

import java.util.*;

public class Main {


    public static void main(String[] args) {
        int[][] land = {
                {1, 0, 1, 0, 1, 1},
                {1, 0, 1, 0, 0, 0},
                {1, 0, 1, 0, 0, 1},
                {1, 0, 0, 1, 0, 0},
                {1, 0, 0, 1, 0, 1},
                {1, 0, 0, 0, 0, 0},
                {1, 1, 1, 1, 1, 1}
        };

        var reuslt = solution(land);

        System.out.println(reuslt);
    }

    public static int solution(int[][] land) {
        int result = 0;

        int[][] searchArea = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        boolean[][] visited = new boolean[land.length][land[0].length];

        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < land[0].length; i++) {
            for (int j = 0; j < land.length; j++) {
                if (visited[j][i] || land[j][i] == 0) {
                    continue;
                }
                var findOil = bfs(land, visited, searchArea, new Integer[]{j, i});
                for (int k = findOil[1]; k <= findOil[2]; k++) {
                    map.put(k, map.getOrDefault(k, 0) + findOil[0]);
                }
            }
        }

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > result) {
                result = entry.getValue();
            }
        }

        return result;
    }

    // 채굴가능 오일, min, max
    public static int[] bfs(int[][] land, boolean[][] visited, int[][] searchArea, Integer[] start) {

        int[] result = new int[]{1, start[1], start[1]};

        LinkedList<Integer[]> list = new LinkedList<>();
        list.add(start);
        visited[start[0]][start[1]] = true;

        while (!list.isEmpty()) {
            var current = list.poll();

            for (int[] search : searchArea) {
                int nextX = current[0] + search[0];
                int nextY = current[1] + search[1];

                if (nextX == land.length || nextY == land[0].length || nextX == -1 || nextY == -1) {
                    continue;
                }

                if (land[nextX][nextY] == 1 && !visited[nextX][nextY]) {
                    list.push(new Integer[]{nextX, nextY});
                    visited[nextX][nextY] = true;
                    result[0]++;

                    if (nextY > result[2]) {
                        result[2] = nextY;
                    }
                }
            }

        }

        return result;
    }

}