[프로그래머스] 석유시추

       문제 요약        

- 문제

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

         아이디어        

 

- bfs 를 돌리는 이유 : 석유 그룹의 종류 판별

- Map 자료구조를 통해 석유 그룹의 종류별 크기를 저장해둔다 

- 그리고 전체 탐색을 하여 각 열을 선택했을 때 어떤지 비교한다 

         소스코드        

import java.util.*;

class Solution {
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    private int rows, cols;
    private Map<Integer, Integer> groupSizes; // 그룹사이즈 이름이 명확하네
    private int[][] groupMap; // 어떤 그룹으로 매핑할 것인지 

    public int solution(int[][] land) {
        rows = land.length;
        cols = land[0].length;
        groupSizes = new HashMap<>();
        groupMap = new int[rows][cols];

        int groupId = 1;

        // 그룹화 및 그룹 크기 계산
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (land[i][j] == 1 && groupMap[i][j] == 0) { // 땅 & 그룹이 지정 안되었다면 새로운 그룹
                    int size = bfs(i, j, groupId, land);
                    groupSizes.put(groupId, size);
                    groupId++;
                }
            }
        }

        // 열별 최대 합산값 계산
        int maxSum = 0;
        for (int col = 0; col < cols; col++) {
            maxSum = Math.max(maxSum, calculateColumnSum(col));
        }

        return maxSum;
    }

    private int bfs(int startX, int startY, int groupId, int[][] land) {
        int size = 0;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{startX, startY});
        groupMap[startX][startY] = groupId;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            size++;

            for (int[] direction : DIRECTIONS) {
                int newX = current[0] + direction[0];
                int newY = current[1] + direction[1];

                if (isValidCell(newX, newY, land) && groupMap[newX][newY] == 0) {
                    groupMap[newX][newY] = groupId;
                    queue.add(new int[]{newX, newY});
                }
            }
        }

        return size;
    }

    private boolean isValidCell(int x, int y, int[][] land) { // 함수로 빼기
        return x >= 0 && x < rows && y >= 0 && y < cols && land[x][y] == 1;
    }

    private int calculateColumnSum(int col) { // column별로 합계 구하기 
        boolean[] visitedGroups = new boolean[groupSizes.size() + 1];
        int columnSum = 0;

        for (int row = 0; row < rows; row++) {
            int groupId = groupMap[row][col];
            if (groupId > 0 && !visitedGroups[groupId]) {
                columnSum += groupSizes.get(groupId);
                visitedGroups[groupId] = true;
            }
        }

        return columnSum;
    }
}