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

문제 링크

 

프로그래머스

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

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

(자세한 예시는 문제 링크에서 확인요망)

석유가 묻힌 땅과 석유 덩어리를 나타내는 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
• 효율성 테스트 케이스 제한사항: 주어진 조건 외 추가 제한사항 없습니다.

입출력 예

land	result
[[0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 1]]	9
[[1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]]	16

 

문제 풀이

[고려사항]

n, m은 최대 500으로, 땅을 최대 500 * 500이다. 최대 250,000(25만)개의 좌표를 매번 순회한다는 등의 계산으로는 시간이 초과할 수 있기에 최대한 효율적인 방식으로 풀어야한다.

[알고리즘, 구현방법]

이 문제는 석유 덩어리를 시추관이 통과하면 석유량에 해당 석유 덩어리의 크기가 누적되고, 그 중 가장 많은 양의 석유를 반환해야한다. 그렇기때문에 일단 1)석유 덩어리를 구하고 2)시추관을 열을 기준으로 땅에 꽂았을때 열 별로 나오는 석유량을 계산 해야한다.

 

1)석유 덩어리 구하기 : BFS

석유가 있는 땅(land[i][j] = 1)에서 석유 덩어리들을 식별하고, 각 덩어리를 객체로 만들어 리스트에 저장했다. 이 덩어리들을 모두 식별해야만 석유 시추 시 정확한 석유량을 계산할 수 있기때문이다. 

[BFS(너비 우선 탐색)를 이용한 석유 덩어리 탐색]

석유 덩어리는 BFS 를 이용해서 탐색했다. 

먼저, land를 끝까지 순회하면서, 석유인(=1) 좌표를 발견하면 새로운 석유 덩어리의 시작이라고 판단한다.

BFS를 이용해서 이 시작이 되는 좌표와 연결된 모든 1을 탐색하고, 이를 하나의석유 덩어리로 묶어서 리스트에 저장했다 .

이렇게 해서 모든 좌표를 순회하면, land 배열에 존재하는 모든 석유 덩어리들을 식별할 수 있다.

 

2)가장 많은 석유를 뽑을 수 있는 시추관 찾기

처음에는 land를 다시 순회하면서 석유가 있는 땅(=1)일 때 분기 처리를 통해 석유량을 계산하는 방법을 생각했다. 그런데 이 방법은 이미 한 번 석유 덩어리를 찾아 순회한 이후, 또다시 땅 전체를 순회해야 하므로 비효율적이다. 땅 전체를 다시 순회하는 것은 시간과 자원의 낭비로 이어지기 때문이다. 

땅 전체를 다시 순회하는 대신, 이미 식별하고 저장해둔 석유 덩어리 정보를 활용하여 석유량을 계산하는 방법으로 계산했다.

이전에 저장해둔 석유 덩어리 객체들에 포함된 좌표들을 활용해서, 각 석유 덩어리의 좌표 중에서 열 값을 기준으로 시추관 별로 뽑을 수 있는 석유량을 계산했다.

이 방법을 통해서 전체 땅을 다시 순회하지 않고, 이미 탐색한 석유 덩어리 좌표만 순회하여서 석유량을 계산할 수 있게된다. 어차피 구해야하는 것은 특정 열에 속한 석유 덩어리 정보이기 때문에, 이를 직접 활용하는 것이 효율적이다. 

 

[풀이 과정]

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

• 땅 배열(land)을 전체 탐색
• 방문한적 없는 좌표이고(좌표 방문 여부 배열 (visited[i][j] = false), 석유가 있는 땅(land[i][j] = 1)이라면 주변 탐색 시작
  
  • Queue에서 좌표를 하나씩 꺼내면서 상하좌우로 인접한 좌표를 확인하여 방문한적 없고 석유가 있는 땅이면 Queue에 추가
  • 이때 석유 덩어리에 포함되는 좌표들이 Queue에 추가되고, 이 좌표들은 동시에 해당 석유 덩어리의 좌표 리스트(pointList)에 추가
• BFS 탐색이 끝나면, 해당 석유 덩어리의 좌표 리스트인 pointList를 석유 덩어리 객체를 담은 리스트(oils)에 저장

2. 가장 많은 석유를 뽑을 수 있는 시추관 찾기

• 저장된 석유 덩어리 리스트(oils)를 순회하며 각 석유 덩어리의 좌표를 확인
• 좌표의 열 값을 기준으로 해당 열에서 시추할 수 있는 석유량 계산
  • 열에 대한 시추관 정보(Drill) 객체를 생성해서 시추할 수 있는 석유량을 누적
  • 특정 열에 있는 석유 덩어리가 아직 누적되지 않았다면, 즉, 아직 해당 열에 해당 석유 덩어리를 계산한 적 없다면, 해당 석유 덩어리의 크기(좌표 리스트의 크기)를 누적합에 더하고, 해당 석유 덩어리를 방문처리한다.

3. 열마다 시추할 수 있는 석유량을 저장한 리스트(drils)를 순회하여 최댓값 찾아서 반환

 

정답 코드

import java.util.*;
public class Solution { 
	public int solution(int[][] land) {
        int n = land.length; // 세로 길이
        int m = land[0].length; // 가로 길이

        boolean[][] visited = new boolean[n][m];
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        // 석유 덩어리 구하기
        Queue<Point> queue = new LinkedList<>();
        List<Oil> oils = new ArrayList<>();
        // BFS 탐색
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && land[i][j] == 1) { // 방문한적 없고, 석유가 있는 땅인 경우
                    visited[i][j] = true;

                    List<Point> pointList = new ArrayList<>(); // 현재 석유 덩어리의 좌표 리스트
                    pointList.add(new Point(i,j));
                    queue.offer(new Point(i,j));

                    while (!queue.isEmpty()) {
                        Point point = queue.poll();

                        for (int k = 0; k < 4; k++) {
                            int nx = point.x + dx[k];
                            int ny = point.y + dy[k];

                            if(nx >= 0 && nx < n && ny >= 0 && ny < m) {
                                if (!visited[nx][ny] && land[nx][ny] == 1) {
                                    visited[nx][ny] = true;
                                    queue.offer(new Point(nx, ny));
                                    pointList.add(new Point(nx, ny));
                                }
                            }
                        }
                    }
                    oils.add(new Oil(pointList)); // 석유 덩어리 리스트에 현재 석유 덩어리 정보 저장
                }
            }
        }

        // 가장 많은 석유를 뽑을 수 있는 시추관 찾기
        Drill[] drills = new Drill[m]; // 열 개수(=가로 길이)만큼 할당
        int oilCnt = oils.size();
        // 석유 덩어리 정보를 저장한 List를 순회하면서 해당 포인트의 열을 기준으로 석유 덩어리 사이즈 계산
        for (int o = 0; o < oilCnt; o++) {
            for (Point point : oils.get(o).pointList) {
                int y = point.y;
                // 아직 생성한적 없다면 석유 덩어리 개수를 매개변수로 넣어서 생성
                if (drills[y] == null) {
                    drills[y] = new Drill(oilCnt);
                }

                if (!drills[y].visitedOil[o]) { // 현재 석유 덩어리가 해당 좌표 열에 아직 누적합 되지 않은 경우
                    drills[y].visitedOil[o] = true; // 방문한 석유 덩어리니까 true 할당
                    drills[y].addOilSum(oils.get(o).pointList.size()); // 현재 석유 덩어리의 크기 누적
                }
            }
        }

        // Max 석유량 찾기
        int max = 0;
        for (Drill drill: drills) {
            // 석유가 없는 열이라면 drill이 null 일 수도 있으므로 null 검증
            if (drill != null && drill.oilSum > max) max = drill.oilSum;
        }
        return max;
    }

    public class Point {
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public class Oil {
        List<Point> pointList;

        public Oil(List<Point> pointList) {
            this.pointList = pointList;
        }
    }

    public class Drill {
        boolean[] visitedOil;
        int oilSum = 0;

        public Drill(int oilCnt) {
            this.visitedOil = new boolean[oilCnt];
        }
        public void addOilSum(int oilSize) {
            this.oilSum += oilSize;
        }
    }
}