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

요구사항

시추관을 세로로 1개 설치 할 때 가장 많은 석유량을 뽑을 수 있는 열의 석유량 구하기

(해당 열의 땅과 연결 된 석유는 모두 합산됨)

 

 

입력 값

int[][] land

탐색할 땅의 정보를 담은 2차원 배열 땅의 정보는 0(=빈땅) 또는 1(석유가 있는 땅) 이며  land[i] 는 i+1 행의 배열 land[i][j]는 i+1 행 j+1 열 땅의 정보

 

풀이

1. 탐색에 사용 될 변수 생성

int landH = land.length; int landV = land[0].length;	전체 땅의 세로 길이, 가로 길이
int[] dfsX = {0, 0, -1, 1}; int[] dfsY = {-1, 1, 0, 0};	BFS 탐색용 x축 y축 배열 순서대로 상 하 좌 우 검색에 사용
boolean[][] checkedLand = new boolean[landH][landV];	탐색 여부 저장 배열
Queue<int[]> que = new LinkedList<>();	상하좌우 탐색 큐
int[] oilCnts = new int[landV];	열 별 추출 가능 석유량 배열
boolean[] oilCols; int oilCnt; int[] now; int x,y;	탐색 loop 내에서 사용될 변수 탐색중인 석유 덩어리가 포함된 열 배열 탐색중인 석유 덩어리의 석유 량 현재 탐색중인 땅 현재 탐색중인 땅의 x,y 좌표

 

2. 모든 땅 탐색을 위해 이중 loop 블럭

 

3. 석유 덩어리 찾기

   -> 처음 탐색하는 땅이고 석유가 있는 경우 상하좌우 탐색 시작을 위해 Queue에 Add

   -> 재 탐색 방지를 위해 탐색 시 마다 탐색 여부 저장

 

4. 석유 덩어리 크기 구하기 (BFS)

   -> 상하좌우 탐색 중에 처음 탐색하는 땅이고 석유가 있는 땅은 Queue에 다시 Add 하여 상하좌우 탐색 반복

   -> 재 탐색 방지를 위해 탐색 시 마다 탐색 여부 저장

   -> 석유가 포함된 열 저장 (oilCols[n] = true)

   -> 석유 덩어리 양 저장 (oilCnt++)

 

5. 탐색 중이던  석유 덩어리의 탐색이 완료되면 석유 덩어리 정보 저장 후 3번 부터 다시 시작

    -> 탐색된 석유 덩어리 크기 열 별 합산  (oilCnts[n] += oilCnt)

 

6. 모든 땅 탐색이 완료 되면 열 별 석유량 정렬하여, 가장 많은 석유량 return

 

728x90

 

Java 코드

import java.util.*;

class Solution {
    public int solution(int[][] land) {
        int answer = 0;
        
        int landH = land.length;
        int landV = land[0].length;
        
        int[] dfsX = {0, 0, -1, 1};
        int[] dfsY = {-1, 1, 0, 0};
        
        boolean[][] checkedLand = new boolean[landH][landV];
        Queue<int[]> que = new LinkedList<>();
        
        int[] oilCnts = new int[landV];
        
        boolean[] oilCols;
        int[] now;
        int oilCnt, x, y;
        
        for(int i = 0; i < landH; i++) {
            for(int j = 0; j < landV; j++) {
                
                // 이미 탐색한 곳이면 pass
                if(checkedLand[i][j]) continue;
                
                // 탐색 여부 저장
                checkedLand[i][j] = true;
                
                // 석유가 없으면 pass
                if(land[i][j] != 1) continue;
                
                oilCnt = 1;
                oilCols = new boolean[landV];
                oilCols[j] = true;
                
                // 탐색용 큐에 추가
                que.add(new int[]{i, j});

                while(!que.isEmpty()) {
                    now = que.poll();
                    y = now[0];
                    x = now[1];

                    // 상하좌우 탐색
                    for(int k = 0; k < 4; k++) {
                        if((y + dfsY[k]) < 0 || (y + dfsY[k]) >= landH      // 상하 범위 이탈
                           || (x + dfsX[k]) < 0 || (x + dfsX[k]) >= landV   // 좌우 범위 이탈
                           || checkedLand[y + dfsY[k]][x + dfsX[k]]         // 이미 탐색
                          ) continue;
                        
                        // 탐색 여부 저장
                        checkedLand[y + dfsY[k]][x + dfsX[k]] = true;
                        
                        // 석유가 없으면 pass
                        if(land[y + dfsY[k]][x + dfsX[k]] != 1) continue;   

                        // 탐색 필요 큐에 추가
                        que.add(new int[]{y + dfsY[k], x + dfsX[k]});

                        // 현재 탐색 석유 증가처리
                        oilCnt++;
                        
                        // 탐색 col 저장
                        oilCols[x + dfsX[k]] = true;
                    }
                }
                
                for(int l = 0; l < oilCols.length; l++){
                    if(oilCols[l]) {
                        oilCnts[l] += oilCnt;
                    }
                }
            }
        }
        
        Arrays.sort(oilCnts);
        answer = oilCnts[oilCnts.length - 1];
        
        return answer;
    }
}

 

 

문제 출처

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