[Coding Test | Programmers] -Oil Drilling (Java)

석유 시추

Approach

This problem required determining the maximum amount of oil by placing a pie once. To figure out amount of oil, it was decided to use BFS for searching the area. And Call this function when the pipe meets oil while going down. this process had to every column in order to figure out maximum.

This solution passed the accuracy test but not the efficiency test. I had to consider how reduce the number of loop.

The reason why the solution didn't pass the accuracy test is that it made a visit array. This process make slow as much as length of column. I change this process by adding group array for store accumulate amount of oil.

Algorithm & Data Structure

BFS, DFS, Set

Time Complexity

O(n * m)

Code

import  java.util.*;

class Solution {
    int[] pipe;
    public int solution(int[][] land) {
        int answer = 0;
        pipe = new int[land[0].length];
        boolean[][] visit = new boolean[land.length][land[0].length];
        for (int i = 0 ; i < land[0].length ; i++){
            int sum = 0;
            // Declare visit to perform a fresh search for each column
            for(int j = 0 ; j < land.length ; j++){
                if (land[j][i] == 1 && visit[j][i] == false){
                    sum += search(land, visit, j, i);
                }
            }
            
        }
        
        for (int line : pipe){
            answer = Math.max(answer, line);
        }
        
        return answer;
    }
    
    
    private int search(int[][] land, boolean[][] visit, int row, int column){
        //Handle visit
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{row, column});
        Set<Integer> group = new HashSet();
        visit[row][column] = true;
        
        int count = 0;
        // Find adjacent nodes of the visited node
        //move all directions
        int[] dColumn = {-1,0,1,0};
        int[] dRow = {0,-1,0,1};
        
        while(!q.isEmpty()){
            int[] position = q.poll();
            group.add(position[1]);
            count++;
            for(int i = 0 ; i < 4 ; i++){
                int nRow = position[0] + dRow[i];
                int nColumn = position[1] + dColumn[i];
                
                //Do not execute out of range
                if (!checkRange(nRow, nColumn, land)){
                    continue;
                }
                
                if (land[nRow][nColumn] == 1 && visit[nRow][nColumn] == false){
                    q.add(new int[]{nRow, nColumn});
                    
                    visit[nRow][nColumn] = true;
                }
            }
        }
        
        for(int gs : group){
            pipe[gs] += count;
        }
        return count;
    }
    
    private boolean checkRange(int row, int column, int[][] land){
        if(row >= land.length || row < 0){
            return false;
        }
        
        if (column >= land[0].length || column < 0){
            return false;
        }
        
        return true;
    }
}