[프로그래머스 - JAVA] PCCP 기출 2번 석유 시추

 

문제

 

세로길이가 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의 길이 = 땅의 세로길이 = n ≤ 100

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

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

 

풀이

 

처음 생각은 전형적인 dfs 문제를 생각하고 풀었고 처음 풀이는 문제는 맞췄지만 효율성이 떨어지는 코드로 작성하게 되었다.

원인으로는 이전에 계산한 값을 다음 조건에서 다시 계산하면서 시간이 오래걸리게 되는 문제가 발생했다. 해당 문제를 해결하려면 이전에 방문해 계산한 값을 저장하고 다시 방문하지 않고 넘어가도록 만들어야한다.

 

오답

 

class Solution {
    
    int x_size, y_size;
    boolean[][] visited;

    public int solution(int[][] land) {
        int answer = 0;
        
        x_size = land[0].length;
        y_size = land.length;
        
        for (int i = 0; i < x_size; i++) {
            int total = 0;
            visited = new boolean[y_size][x_size];
            for (int j = 0; j < y_size; j++) {
                if (land[j][i] == 1 && !visited[j][i]) {
                    total += dfs(land, i, j);
                    answer = Math.max(answer, total);
                }
            }
        }
        
        return answer;
    }
    
    public int dfs(int[][] land, int x, int y) {
        if (x < 0 || x >= x_size || y < 0 || y >= y_size || land[y][x] == 0 || visited[y][x]) {
            return 0;
        }
        
        visited[y][x] = true;
        
        int size = 1;
        
        size += dfs(land, x + 1, y);
        size += dfs(land, x - 1, y);
        size += dfs(land, x, y + 1);
        size += dfs(land, x, y - 1);
        
        return size;
    }
}

 

정답

 

import java.util.*;

public class Solution {

    int x_size, y_size;
    boolean[][] visited;
    HashMap<Integer, Integer> oilClusters = new HashMap<>();
    int[][] clusterId; 
    int clusterCount = 0;

    public int solution(int[][] land) {
        int answer = 0;
        
        x_size = land[0].length;
        y_size = land.length;
        
        visited = new boolean[y_size][x_size];
        clusterId = new int[y_size][x_size];
        
        // 초기화
        for (int[] row : clusterId) {
            Arrays.fill(row, -1);
        }
        
        // 모든 석유 덩어리를 찾아 크기를 저장
        for (int i = 0; i < y_size; i++) {
            for (int j = 0; j < x_size; j++) {
                if (land[i][j] == 1 && clusterId[i][j] == -1) {
                    int size = dfs(land, j, i, clusterCount);
                    oilClusters.put(clusterCount, size);
                    clusterCount++;
                }
            }
        }
        
        // 각 열에 시추관을 설치해 뽑을 수 있는 석유량 계산
        for (int j = 0; j < x_size; j++) {
            int oilAmount = 0;
            Set<Integer> visitedClusters = new HashSet<>();
            for (int i = 0; i < y_size; i++) {
                int id = clusterId[i][j];
                if (id != -1 && !visitedClusters.contains(id)) {
                    oilAmount += oilClusters.get(id);
                    visitedClusters.add(id);
                }
            }
            answer = Math.max(answer, oilAmount);
        }
        
        return answer;
    }
    
    public int dfs(int[][] land, int x, int y, int id) {
        if (x < 0 || x >= x_size || y < 0 || y >= y_size || land[y][x] == 0 || clusterId[y][x] != -1) {
            return 0;
        }
        
        clusterId[y][x] = id;
        
        int size = 1;
        
        size += dfs(land, x + 1, y, id);
        size += dfs(land, x - 1, y, id);
        size += dfs(land, x, y + 1, id);
        size += dfs(land, x, y - 1, id);
        
        return size;
    }

}

 

별도의 Hash값을 이용해 방문 여부를 계산하고 해당 값을 더 계산하지 않고 더해주는 방식으로 시간 효율성을 개선하였다.