[프로그래머스/Java] 석유 시추(pccp 기출 문제)

---

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

프로그래머스

석유 시추를 하는 과정에서 석유량 계산을 어떻게 해야할지 고민하는 과정에서 시간이 좀 걸렸던 문제였습니다.

 

고찰 과정

land의 길이의 최댓값이 500이므로 이중 반복문을 통해서 석유가 있는 곳을 시점으로 bfs(Breadth-first search)를 통해 land의 상하좌우를 탐색하여 석유량을 계산합니다. 여기서 land의 각 열마다 영역마다 구분된 석유량을 더한 값을 구해주어야 하므로 영역 구분을 인덱스로 취급하는 또다른 Map을 만들어서 해당 영역에 존재하는 석유량 정보를 매핑합니다. 그리고 영역 구분을 위해서 land와 크기와 같은 area 이차원 배열을 만들어서 영역 정보를 저장합니다.

 

그렇게 해서 bfs를 통해서 Map에 석유량 정보가 전부 저장이 되었으면 area를 활용해서 각 열에 존재하는 석유 영역에서의 석유량의 합을 계산해서 총 석유량의 최댓값을 도출했습니다.

 

---

코드

import java.util.*;

class Pair {
    private final int x;
    private final int y;
    
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public int getX() {
        return x;
    }
    
    public int getY() {
        return y;
    }
}

class Solution {
    
    private static final int NOTHING = 0;

    private int[] dx = {-1, 0, 1, 0};
    private int[] dy = {0, 1, 0, -1};
    
    public int solution(int[][] land) {
        int answer = NOTHING;
        int rowLen = land.length;
        int colLen = land[0].length;
        int[][] area = new int[rowLen][colLen];
        int areaNumber = 1;
        Map<Integer, Integer> oilMap = new HashMap<>();
        
        for (int i = 0; i < rowLen; ++i) {
            for (int j = 0; j < colLen; ++j) {
                if (land[i][j] == NOTHING || area[i][j] != NOTHING) {
                    continue;
                }
                
                int oilAccount = bfs(land, area, i, j, areaNumber);
                oilMap.putIfAbsent(areaNumber++, oilAccount);
            }
        }
        
        boolean[] visited = new boolean[areaNumber];
        
        for (int c = 0; c < colLen; ++c) {
            int oilSum = 0;
            
            for (int r = 0; r < rowLen; ++r) {
                if (area[r][c] == 0) {
                    continue;
                }
                
                if (visited[area[r][c]]) {
                    continue;
                }
                
                visited[area[r][c]] = true;
                oilSum += oilMap.get(area[r][c]);
            }
            
            if (answer < oilSum) {
                answer = oilSum;
            }
            
            Arrays.fill(visited, false);
        }
        
        return answer;
    }
    
    private int bfs(int[][] land, int[][] area, int row, int col, int areaNumber) {
        Queue<Pair> q = new ArrayDeque<>();
        q.offer(new Pair(row, col));
        area[row][col] = areaNumber;
        int value = land[row][col];
        
        while (!q.isEmpty()) {
            Pair p = q.poll();
            int x = p.getX();
            int y = p.getY();
            
            for (int dir = 0; dir < 4; ++dir) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                
                if (nx < 0 || ny < 0 || nx >= area.length || ny >= area[0].length) {
                    continue;
                }
                
                if (land[nx][ny] == NOTHING || area[nx][ny] != NOTHING) {
                    continue;
                }
                
                area[nx][ny] = areaNumber;
                value += land[nx][ny];
                q.offer(new Pair(nx, ny));
            }
        }
        
        return value; 
    }
}