Lv.2 : [PCCP 기출문제] 2번

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• n x m 크기의 땅에 석유 덩어리들이 있다. 어느 지점에서 시추해야 가장 많은 석유를 시추하는지 구한다.
• 시추는 가장 위에서 수직으로 하는데, 시추기가 지나가는 석유 덩이리를 모두 시추할 수 있다.

🔸 문제 풀이 🔸

• 석유 덩어리를 처음 발견했을때 다음과 같이 처리한다.
  • 석유 덩어리 번호를 붙인다.
  • 해당 덩어리의 크기를 탐색해 파악하고, 번호에 맞게 크기를 저장해둔다.
• 마지막에 모든 지점에서 시추해보며, 시추 되는 석유량의 최대값을 반환한다.

---

🔸 코드 🔸

import java.util.Queue;
import java.util.ArrayDeque;

class Solution {
    private static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int solution(int[][] land) {
        int n = land.length;
        int m = land[0].length;
        int[][] map = new int[n][m]; // 석유 덩어리 별 숫자 부여
        int[] oils = new int[n * m + 1]; // 석유 번호 별 석유량
        int oileCnt = 0; // 체크한 덩어리 수

        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (land[i][j] == 1 && map[i][j] == 0) { // 처음 석유 덩어리 발견

                    oileCnt++;
                    int cnt = 1;

                    // BFS
                    Queue<Point> que = new ArrayDeque<>();
                    que.add(new Point(i, j));
                    map[i][j] = oileCnt;

                    while (!que.isEmpty()) {
                        Point point = que.poll();
                        for (int k = 0; k < dx.length; k++) {
                            int row = point.x + dx[k];
                            int col = point.y + dy[k];

                            if (0 <= row && row < n && 0 <= col && col < m && land[row][col] == 1
                                && map[row][col] == 0) {
                                map[row][col] = oileCnt;
                                cnt++;
                                que.add(new Point(row, col));
                            }
                        }
                    }
                    // 현재 기름 덩어리 번호에 크기 저장
                    oils[oileCnt] = cnt;
                }
            }
        }

        int answer = 0;

        for (int i = 0; i < m; i++) { // 최대가 되는 시추 지점 찾기
            boolean[] check = new boolean[oileCnt + 1];
            int sum = 0;

            for (int j = 0; j < n; j++) {
                if (!check[map[j][i]]) {
                    check[map[j][i]] = true;
                    sum += oils[map[j][i]];
                }
            }
            answer = Math.max(answer, sum);
        }

        return answer;
    }
}

🔸 코드 해석 🔸

• 석유 덩어리 번호를 해당 덩어리의 모든 지점에 기록해둔다.
  • 처음 석유 덩어리를 발견했을 때, BFS를 통해 크기를 파악한다.
• 시추량이 최대가 되는 석유량을 구한다.
  • boolean 배열 check를 덩어리 개수 만큼 만들어, 한 번의 시추에서 이미 파악한 덩어리라면, 합산하지 않는 방식으로 계산한다. 

---

🔸 end 🔸

• PCCP에서 풀었던 문제인데, 이번에 기출로 공개되어서 다시 한 번 풀게 되었다.
  • 시험에서 풀 때도 맞았었는데, 그냥 기초적인 BFS문제여서 간단히 풀이할 수 있었다.
• 다른 풀이들도 비슷하게 풀이한 것 같다.