[PCCP 기출문제] 2번 / 석유 시추 [JAVA]

문제분석

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

프로그래머스

 

n*m 보드에 석유가 있는 곳을 1으로 나타내고, 각 상하좌우 기준 인접 석유끼리는 하나의 집합으로 여길 수 있다.

각 col (m line)에 대해서 시추관을 넣을 때 팔 수 있는 최대 석유의 양을 구하는 문제

 

아주 포멀한 bfs문제다.

 

전체 배열 원소에 대해 석유가 있다면 (1이라면)

bfs로 상하좌우에 대해 인접 포인트 중 방문하지 않았고 석유가 있는 포인트를 탐색 대상에 추가해 나가며 석유 집합을 찾고

 

해당 집합에 포함된 col에 현재 집합의 석유의 양을 더해주고, 각 col의 값과 현재 최댓값을 비교해가며 갱신하면 답을 구할 수 있다.

 

다만, 처음에는 visit정보에 대해 Point 객체에 대한 HashSet으로 비교를 하였으나..

 

계속 효율성에서 시간초과가 나길래 이렇게 저렇게 테스트를 해봐도 주어진 제한시간 10초를 넘기진 않았다..

그러다, 설마 싶어 boolean 배열로 바꿔 다시 돌려보니 바로 통과됐다..

(bfs할땐 앵간하면 boolean으로 비교하자..)

 

 

코드

import java.util.*;
class Solution {
    public int solution(int[][] land) {
        int answer = 0;
        
        //find fuel set
        //add col to fuel amount
        int n = land.length;
        int m = land[0].length;
        
        // n=500;
        // m=500;
        // land = new int[n][m];
        // for(int i=0; i<n;i++){
        //     for(int j=0; j<m; j++){
        //         // land[i][j] = Math.random() > 0.9 ? 0 : 1;
        //         land[i][j] = i%2;
        //     }
        // }
        
        int[] fuelInCol = new int[land[0].length];
        boolean[][] isChecked = new boolean[n][m];
        
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,-1,1};
        
        // Set<Point> visitPoints = new HashSet<>();
        boolean[][] visited = new boolean[n][m];
        Set<Point> fastSet = new HashSet<>();
        
        for(int i=0; i<n;i++){
            for(int j=0; j<m; j++){
                // if(visitPoints.contains(new Point(i,j)))
                //     continue;
                if(visited[i][j] || land[i][j] == 0)
                    continue;
                
                int fuelAmount = 0;
                Set<Integer> colNums = new HashSet<>();
                
                
                Queue<Point> queue = new LinkedList<>();
                queue.add(new Point(i,j));
                visited[i][j] = true;
                // visitPoints.add(new Point(i,j));
                
                
                while(!queue.isEmpty()){
                    Point point = queue.poll();
                    // fastSet.add(point);
                    // if(visitPoints.contains(point))
                    //     continue;
                    // visitPoints.add(point);
                    
                    fuelAmount++;
                    colNums.add(point.y);
                    
                    for(int k=0; k<4;k++){
                        int nx = point.x+dx[k];
                        int ny = point.y+dy[k];
                        Point next = new Point(nx,ny);
                        if(nx >=0 && ny >=0 && nx < n && ny < m && !visited[nx][ny] && land[nx][ny] == 1){
                            queue.add(next);
                            visited[nx][ny] = true;
                            // visitPoints.add(next);
                            // fastSet.add(next);
                        }
                    }
                }
                
                for(int col : colNums){
                    fuelInCol[col] += fuelAmount;
                    answer = Math.max(fuelInCol[col], answer);
                }
                
            }
        }
        
        
        return answer;
    }
    public class Point{
        int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        
        }
        
        @Override
        public boolean equals(Object o){
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x==point.x && y==point.y;
        }
        @Override
        public int hashCode(){
            return Objects.hash(x,y);
        }
    }
}