[PCCP 기출 2번] 석유 시추

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

프로그래머스

 

문제 유형

• BFS
• 누적합

문제 난이도 

• Lev2

문제 분석

주어진 조건
시추관을 수직으로 뚫어서 시추관과 인접한 석유 덩어리들의 크기들을 모두 합한 결과가 가장 큰 경우의 석유량을 구하는 문제이다.

단순하게 완전 탐색을 생각한다면 방문하지 않은 좌표들 가운데, 석유가 있는 공간을 찾고, 그 공간과 인접한 석유 덩어리들의 합을 해당 열에 더해서 Max 값을 구하는 방법을 처음 생각했다.
당연하게 시간 초과다.
최악의 경우: 좌표 탐색: O(500*500) * BFS 순회 O(500*500) => O(625 * 10^8)

따라서 누적합을 생각해보았다. 가로만 순회하면서 해당 가로에 있는 석유 덩어리들의 합들을 가로마다 누적합을 통해 더해주고, 지나간 위치들은 방문처리를 한다. 다음과 같이 진행할 경우, 이전보다 시간 단축이 가능하다.

 

전체 코드

import java.io.*;
import java.util.*;

class Solution {
    static ArrayDeque<int[]> q;
    
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int N, M;
    static int[] sum;
    static boolean[][] visited;
    public int solution(int[][] land) {
        int result = 0;
        
        N = land.length;
        M = land[0].length;
        sum = new int[M];
        
        // 0이면 빈 땅, 1이면 석유
        visited = new boolean[N][M];
        
        for(int i = 0; i < M; i++) {
           BFS(i, visited, land);
        }
        
        Arrays.sort(sum);
        
        return sum[sum.length-1];
        
    }
    
    static void BFS(int col, boolean[][] visited, int[][] land) {
        ArrayDeque<int[]> q = new ArrayDeque<>();
        
        for(int i = 0; i < N; i++) {
            int maxCol = col;
            int cnt = 0;
            
            if(land[i][col] == 0) continue;
            if(visited[i][col]) continue;
            
            
            if(land[i][col] == 1 && !visited[i][col]) {
                q.offer(new int[]{i, col});
                visited[i][col] = true;
                
                while(!q.isEmpty()) {
                    
                    int[] p = q.poll();
                    cnt++;
                    
                    for(int d = 0; d < 4; d++) {
                        int nx = p[0] + dx[d];
                        int ny = p[1] + dy[d];
                        
                        if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                        
                        if(visited[nx][ny] || land[nx][ny] == 0) continue;
                        
                        visited[nx][ny] = true;
                        q.offer(new int[]{nx, ny});
                        
                        if(maxCol < ny) maxCol = ny;
                    }
                }
            }
            
            if(cnt != 0) {
                for(int j = col; j <= maxCol; j++) {
                    sum[j] += cnt;
                }    
            }            
        }
    }
}