[프로그래머스] [PCCP 기출문제] 2번 / 석유 시추 - Java

문제

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

프로그래머스

 

---

 

문제 개요

문제는 세로 n, 가로 m의 격자에서 석유가 묻힌 땅을 분석하여, 수직으로 한 줄 시추관을 설치했을 때 뽑을 수 있는 석유량이 최대가 되는 위치를 찾는 것입니다.
석유는 상하좌우로 연결된 1의 집합(덩어리)로 표현됩니다. 시추관이 지나는 열에서 해당 석유 덩어리에 포함된 모든 석유를 뽑을 수 있습니다.
최종적으로, 각 열에 대해 가능한 석유량을 계산하고 그중 최대값을 반환합니다.

 

접근 방법

1. 덩어리 구분 및 크기 계산

• 주어진 격자 land에서 석유가 묻힌 영역(값이 1)을 BFS를 사용해 탐색하며 각 석유 덩어리의 크기를 계산합니다.
• 탐색 중 발견된 석유 덩어리를 특정 문자('A', 'B'...)로 표시하여 덩어리를 구분합니다.
• 각 덩어리의 크기는 regionSize라는 해시맵에 저장하여, 나중에 쉽게 크기를 참조할 수 있습니다.

2. 시추관 열별 석유량 계산

• 각 열(column)을 순회하며, 해당 열을 지나는 석유 덩어리들의 크기를 합산합니다.
• 이를 위해, 현재 열에 포함된 유일한 석유 덩어리의 구분 문자를 확인합니다.
• 합산한 석유량을 answer 변수에 저장하고, 이를 계속 업데이트하여 최댓값을 유지합니다.

import java.util.*;

class Solution {
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static char[][] map;
    static boolean[][] visited;
    static Map<Character, Integer> regionSize;

    public int solution(int[][] land) {
        int answer = 0;
        int rows = land.length, cols = land[0].length;
        map = new char[rows][cols];
        visited = new boolean[rows][cols];
        regionSize = new HashMap<>();
        
        char region = 'A';
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (land[i][j] == 1 && !visited[i][j]) {
                    markRegion(i, j, region++, land);
                }
            }
        }

        for (int col = 0; col < cols; col++) {
            Set<Character> uniqueRegions = new HashSet<>();
            for (int row = 0; row < rows; row++) {
                if (map[row][col] >= 'A') {
                    uniqueRegions.add(map[row][col]);
                }
            }
            int sum = uniqueRegions.stream().mapToInt(regionSize::get).sum();
            answer = Math.max(answer, sum);
        }
        return answer;
    }

    private void markRegion(int startRow, int startCol, char region, int[][] land) {
        Queue<int[]> queue = new LinkedList<>();
        List<int[]> cells = new ArrayList<>();
        queue.add(new int[]{startRow, startCol});
        visited[startRow][startCol] = true;
        int size = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int r = current[0], c = current[1];
            map[r][c] = region;
            size++;
            cells.add(current);

            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr >= 0 && nr < land.length && nc >= 0 && nc < land[0].length 
                    && land[nr][nc] == 1 && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    queue.add(new int[]{nr, nc});
                }
            }
        }

        regionSize.put(region, size);
    }
}