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

<목차>

1. 문제
2. 접근 방법
3. 풀이 소스

 

[문제]

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

 

 

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

 

 

시추관의 위치	획득한 덩어리	총 석유량
1	8	8
2	8	8
3	8	8
4	7	7
5	7	7
6	7	7
7	7,2	9
8	2	2

ㅇ

오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.
석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

---

제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
  • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
  • land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
  • land[i][j]는 0 또는 1입니다.
  • land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.

정확성 테스트 케이스 제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
• 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

---

[접근 방법]

시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다.

1. 컬럼 기준으로 시추량이 정해진다.
2. 깊이 우선 탐색(DFS) 활용하여, 각 매장 지점 별 {최소 컬럼, 최대 컬럼, 총 매장량} 형태의 List 추출
3. 컬럼 별 매장량 확인하며, 최대 매장량 탐색

최대 매장량만 알아내면 되기 때문에, 컬럼의 인덱스는 고려하지 않아도 됨

 

<Example>

문제의 예시

DFS 활용하여 {최소 컬럼, 최대 컬럼, 총 매장량} 확인

{0, 2, 8}

{3, 7, 7 }

{6, 7, 2 }

 

---

[풀이 소스]

static List<int[]> oilList = new ArrayList<>();	//{최소 컬럼, 최대 컬럼, 매장량}
static boolean[][] visited;
static int minCol, maxCol, value;

public int solution(int[][] land) {

    //기방문 지점 확인
    visited = new boolean[land.length][land[0].length];
    for(int i = 0; i < land.length; i++) {
        for(int j = 0; j < land[i].length; j++) {

            if(land[i][j] == 1 && !visited[i][j]) {
                minCol = j;
                maxCol = j;
                value = 0;

                dfs(i, j, land);

                if(value > 0) {
                    // 시추 지점 별 최소 컬럼, 최대 컬럼, 매장량 합계 확인 
                    oilList.add(new int[] {minCol, maxCol, value});
                }

            }
        }
    }
    //column 최소 인덱스 오름차순 정렬
    oilList.sort((o1, o2) -> {
        int compare = o1[0] - o2[0];
        if(compare == 0) {
            return o1[1] - o2[0];
        }
        return compare;
    });

    //최대로 시추할 수 있는 컬럼 탐색 
    int max = 0;
    int sum = 0;
    for(int i = 0; i < land[0].length; i++) {

        sum = 0;
        for(int[] oil : oilList) {
            if(i < oil[0]) {
                break;
            }
            if(i >= oil[0] && i <= oil[1]) {
                sum += oil[2]; 
            }
        }
        if(sum > max) {
            max = sum;
        }
    }

    return max;
}

//
public void dfs(int row, int col, int[][] land) {

    //기방문 or 범위밖
    if(row < 0 || row >= land.length || col < 0 || col >= land[0].length || visited[row][col]) {
        return;
    }
    visited[row][col] = true;

    if(land[row][col] == 1) {
        value++;
        if(col < minCol) minCol = col;
        if(col > maxCol) maxCol = col;
        //상 하 좌 우
        dfs(row - 1, col, land);
        dfs(row + 1, col, land);
        dfs(row, col - 1, land);
        dfs(row, col + 1, land);
    }
}