[JAVA] 석유 시추

석유 시추

링크

프로그래머스

 

난이도 : Level 2

유형 : BFS, DP

코딩테스트 연습 > PCCP 기출문제 > 석유 시추

 

풀이

열 하나를 관통할 때 통과하는 석유 덩어리들의 크기의 합이 가장 큰 경우의 수를 구하는 문제

석유 덩어리의 크기는 BFS로 구했다.

그리고 통과할때마다 덩어리 크기를 구하면 시간초과가 나기때문에 DP개념을 이용해 이미 크기를 구한 덩어리의 정보를 저장하며 시간복잡도를 줄였다.

처음 보는 석유 덩어리를 만나면 id, 크기를 map에 저장해놓고 석유 덩어리에 포함되는 x, y 좌표에 id를 저장해놓는 식으로.

그리고 각 열을 순회하면서 해당 좌표에 id가 저장되어 있으면 크기를 더하고 이미 해당 열에서 사용된 id면 무시하게 했다.

 

코드

import java.util.*;

class Solution {
    public int solution(int[][] land) {
        int rows = land.length;
        int cols = land[0].length;
        boolean[][] visited = new boolean[rows][cols]; // 방문 여부 저장
        Map<Integer, Integer> oilSizes = new HashMap<>(); // 덩어리 ID와 크기 저장
        int[][] groupMap = new int[rows][cols]; // 각 칸이 속한 덩어리 ID 저장
        int groupId = 1; // 덩어리 ID
        int maxOil = 0;
        
        // BFS를 사용하여 덩어리별 석유 크기 계산
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (land[i][j] == 1 && !visited[i][j]) {
                    int size = bfs(land, visited, groupMap, i, j, groupId);
                    oilSizes.put(groupId, size);
                    groupId++;
                }
            }
        }

        // 각 열별 최대 석유량 계산
        for (int j = 0; j < cols; j++) {
            Set<Integer> set = new HashSet<>();
            int totalOil = 0;

            for (int i = 0; i < rows; i++) {
                if (groupMap[i][j] > 0 && set.add(groupMap[i][j])) {
                    totalOil += oilSizes.get(groupMap[i][j]);
                }
            }
            maxOil = Math.max(maxOil, totalOil);
        }

        return maxOil;
    }

    public int bfs(int[][] land, boolean[][] visited, int[][] groupMap, int x, int y, int groupId) {
        int size = 0;
        Queue<int[]> queue = new LinkedList<>();
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        
        queue.add(new int[]{x, y});
        visited[x][y] = true;
        groupMap[x][y] = groupId;

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

            for (int i = 0; i < 4; i++) {
                int newX = node[0] + dx[i];
                int newY = node[1] + dy[i];

                if (newX >= 0 && newX < land.length && newY >= 0 && newY < land[0].length) {
                    if (!visited[newX][newY] && land[newX][newY] == 1) {
                        visited[newX][newY] = true;
                        queue.add(new int[]{newX, newY});
                        groupMap[newX][newY] = groupId;
                    }
                }
            }
        }
        return size;
    }
}