[프로그래머스] PCCP 기출문제 2번 (석유 시추) / 자바(Java)

문제

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

프로그래머스

 

---

해설

PCCP의 기출문제로 석유시추라는 이름을 가진 문제입니다.

 

제한 사항에 정확성과 효율성을 확인하는 부분이 있어 조건에 맞도록 구현 뿐 아니라 가능한 효율적이도록 코드를 짜야합니다.

 

시추관은 특정 열을 모두 관통하는데 해당 열에 포함된 석유 덩어리를 모두 시추가 가능합니다. 

하나의 시추관을 사용할 때 시추가능한 최대 석유의 양을 구하는 문제입니다.

 

문제를 해결하기 위해선 각 열별로 시추관을 내려보내며 석유 덩어리를 발견하면 중복된 덩어리를 건드리지 않으며 시추되지 않은 덩어리라면 석유값을 더해 최대값을 구해야 합니다.

 

필요한 작업들을 분해한다면

 

 

1. 열 별로 시추관을 내려보내 연결된 덩어리를 확인해 시추 가능한 총 석유량 확인하기

 

2. 석유 덩어리의 석유 매장량 확인하기

 

 

2가지로 나눠볼 수 있습니다.

 

---

1. 열 별로 시추관을 내려보내 연결된 덩어리를 확인해 시추 가능한 총 석유량 확인하기

 

 

각 열 별로 시추관을 내려보내며 만나는 석유 덩어리를 확인합니다.

 

우선 효율성을 위해 석유 덩어리에 식별 번호를 붙이려고 합니다.

석유 덩어리의 모습은 바뀌지 않기 때문에 식별 번호를 통해 해당 석유덩어리의 총 석유값을 한번씩 만 구할 수 있고 시추관별로 석유 덩어리를 만났는가 여부를 판단할 수 있습니다.

식별된 석유덩어리는 land배열에서 1이 아닌 임의의 식별번호(number)를 입력하여 구별가능하도록 합니다.

식별 번호를 이용해 해당 석유 덩어리의 총 석유값을 저장해주는 배열을 작성합니다. 

배열명		index의 의미	배열 값의 의미	배열의 길이
value	1차원 int 배열	임의로 지정된 석유덩어리 번호	해당 석유 덩어리의 총 석유 값	n*m + 2
checker	1차원 boolean 배열	임의로 지정된 석유덩어리 번호	특정 열의 시추관이 해당 석유 덩어리를 만났는가 중복여부 판단	n*m + 2

 

여기서 배열의 길이가 n*m +2 인 이유는 문제의 입력에서 빈땅은 0, 기본 석유는 1 로 주어져 석유 덩어리의 식별 번호는 2부터 시작합니다. 변수 number를 2로 설정하고 새로운 석유 덩어리를 발견할 때 해당 정보를 number의 숫자로 식별 번호를 부여 후 number를 다음 값으로 늘려줍니다.

 

 

내려가면서 만나는 값은 3가지 가능성이 있습니다.

 

1. 석유가 아닌 땅 또는 시추된 석유덩어리 (land[r][c]  == 0 || checker[ land[r][c] ] )

무시하고 아래로 계속 넘어갑니다. 

 

2. 식별되지 않은 석유덩어리 ( land[r][c] == 1 )

식별번호를 부여하고 총 석유값을 계산해 배열에 추가합니다. 이번 열의 총 합에 총 석유값을 추가합니다. 이번 열의 석유덩어리 방문 여부를 변경합니다.

 

3. 식별 되었으며 시추되지 않은 석유덩어리 ( land[r][c] != 1 &&  land[r][c]  != 0 && !checker[ land[r][c] ]  )

이미 식별되었으므로 총 석유값의 추가와 석유 덩어리 방문여부를 변경합니다.

 

 

---

2. 석유 덩어리의 석유 매장량 확인하기

 

위의 식별되지 않은 석유덩어리를 만난 경우에서 식별번호 부여 및 총 석유값을 계산해 배열에 추가하는 작업이 필요합니다.

 

BFS를 사용해 land 배열을 4방 탐색하며 인접한 미식별석유(1)을 식별번호(number)로 변경하며 총 석유값(chunk)을 얻습니다. 

 

BFS가 종료된 후 

value[number] 에 총 석유값 (chunk)를 입력해 해당 석유덩어리에서 필요한 정보를 저장합니다.

 

number값에 1을 추가하여 다음 식별번호로 사용 가능하도록 변경합니다.

 

 

---

 

식별 변호를 가진 배열 2개를 이용하여 시추관별 확인을 할 때 미식별된 석유 덩어리를 그때그때 확인해 최적의 효율성을 찾을 수 있었습니다.

 

---

코드

import java.util.*;
class Solution {
    public int solution(int[][] land) {
        int answer = 0;
        int n = land.length;
        int m = land[0].length;
        int[] rx = {-1,0,1,0};
        int[] cx = {0,1,0,-1};
        
        // 인덱스는 발견한 덩어리에 임의로 지정한 식별 번호(0,1은 기본적으로 제공되어 2부터 시작)
        // 값은 덩어리에서 얻는 총 석유량
        int[] value = new int[n*m+2];
        int number = 2;
        
        // 해당 덩어리에서 이미 석유를 얻었는가 판별을 위한 배열(인덱스는 식별번호)
        boolean[] checker = new boolean[n*m+2];
        
        // 시추관이 하나씩 이동하며 탐색
        for(int c=0;c<m;c++){
            int sum = 0;
            Arrays.fill(checker,false);
            
            for(int r=0;r<n;r++){
                // 빈땅이거나 이미 얻은 덩어리라면 다음칸으로 넘어감
                if(land[r][c]==0 || checker[land[r][c]]) continue;
                
                // 이전에 발견한 덩어리이면서 아직 얻지 않은 덩어리인 경우
                if(land[r][c]!=0 && land[r][c]!=1 && !checker[land[r][c]]){
                    sum += value[land[r][c]];
                    checker[land[r][c]]=true;
                    continue;
                }
                
                // 지금까지 발견되지 않은 덩어리인 경우 - 식별번호를 주고 덩어리에서 얻는 석유값을 구한다.
                if(land[r][c]==1){
                    Queue<Integer[]> q = new LinkedList<>();
                    int chunk = 1;
                    q.add(new Integer[] {r,c});
                    land[r][c] = number;
                    
                    while(!q.isEmpty()){
                        Integer[] cur = q.poll();
                        
                        for(int i=0;i<4;i++){
                            int nr = cur[0] + rx[i];
                            int nc = cur[1] + cx[i];
                            
                            if(nr>=0 && nr<n && nc>=0 && nc<m && land[nr][nc]==1) {
                                q.add(new Integer[] {nr,nc});
                                land[nr][nc] = number;
                                chunk++;
                            }
                        }
                    }
                    value[number]  = chunk;
                    
                    sum+=chunk;
                    checker[number] = true;
                    number++;
                }
            }
            answer = Math.max(sum,answer);
        }
        
        return answer;
    }
}