[PCCP 기출문제] 석유 시추

 

 

문제 분석:

 

1. 석유가 고여있는 부분을 그룹화한다.

2. 주어진 모든 열을 시추를 하였을때,  가장 많이 석유를 뽑을수 있는 열을 고른다.

 

 

문제의 독해력도 어렵진 않고 , 구현법은  DFS/BFS 만 알고 있으면 풀 수 있는 문제다.

 

 

단,  효율성이 걸려있기때문에  어떻게 완전탐색 로직을 최적화 할지는 고민해봐야한다.

 

단순하게 생각해서  1번열부터 8번열까지 시추를 시작하여,

 

석유블록을 발견할때마다  완전탐색(채굴)을 행한뒤 , 가장 높은 석유량을 기록하는 값을 구하면된다.

 

하지만, 다음과같이 전략을 잡는다면,  이미 1번열에서 채굴한 정보를 2번에서 또다시 채굴을 한다.

 

즉, 중복이 많이일어난다.

 

 

좀 더 효율적인 접근 

 

=> 그렇다면 이미 한번 석유채굴한 구역은  메모이제이션 =>  어딘가에 저장해둔다.

 

제일 첫번째 구역을 A구역, 두번째구역을 B구역..  처럼 라벨링을 한 후, 채굴량을 기록해둔다.

 

EX )  A:  8  ,  B : 7  C : 2

 

이후, 1열부터 채굴을 할때,  A구역을 시추하려 할때,  완전탐색을 하지않고, 이미 구해둔 정보를 가져온다.

 

  

 

문제 풀이

import java.util.*;
class Solution {
    
    boolean[][] visited ;
    int[] dx= {0,1,0,-1};
    int[] dy= {1,0,-1,0};
    int cur =1;
    int[][] map;
    
    int count=0;
    
    // 그룹화된 석유의 수량체크
    Map<Integer,Integer> group = new HashMap<>();
    
    public  int solution(int[][] land) {
        int answer = 0;
        
        map = new int[land.length][land[0].length];
        
        visited = new boolean[land.length][land[0].length];
        
        //석유를 그룹화시키기
        for(int i=0;i<land.length;i++){
            for(int j=0;j<land[0].length;j++){
                if(land[i][j]==1&&!visited[i][j]){
                    visited[i][j]=true;
                    search(i,j,land);
                    group.put(cur,count);
                    cur++;
                    count=0;
                }
            }
        }
        
        //석유 시추 시작
        for(int i=0;i<land[0].length;i++){
            
            Set<Integer> dist = new HashSet<>();
            int sum=0;
            for(int j=0;j<land.length;j++){
                            
                if(land[j][i]==1&&!dist.contains(map[j][i])){
                    
                    dist.add(map[j][i]);
                   
                    sum+=group.get(map[j][i]);        
                }
            }
           
            answer=Math.max(answer,sum);
        }
        
        
        
        return answer;
    }
    
    public void search(int y ,int x, int[][] land){
        count++;
        map[y][x]=cur;
        
        for(int i=0;i<4;i++){
            
            int nx= x+dx[i];
            int ny= y+dy[i];
            
              
            
            if(nx>=0&&nx<land[0].length&&ny>=0&&ny<land.length){
                
                
                if(land[ny][nx]==0||visited[ny][nx]){
                    continue;
                }
                
                visited[ny][nx]=true;
                
             
                search(ny,nx,land);
             
            }
            
        }
        
        
    }
}