[PCCP 기출문제] 2번 / 석유 시추 - JAVA

문제

세로 길이 nnn, 가로 길이 mmm인 격자 모양의 땅 속에서 석유가 여러 덩어리로 묻혀 있습니다. 상·하·좌·우로 연결된 1이 하나의 덩어리가 되며, 덩어리 크기는 포함된 칸의 개수입니다.
당신은 시추관을 단 하나만 세로 방향으로 뚫을 수 있으며, 시추관이 지나가는 열에 포함된 모든 덩어리의 크기를 합산하여 얻는 기름량을 계산합니다.
즉, 각 열(column)마다 그 열을 통과하는 덩어리들의 크기를 모두 더한 값이 “해당 열에서 뽑을 수 있는 기름량”이 되며, 이 중 가장 큰 값을 찾아 반환해야 합니다.

---

풀이 방식

1. 연결 요소(덩어리) 레이블링
   • 먼저 격자 전체를 한 번만 훑어가며, 아직 방문되지 않은 1을 만나면 새로운 ID(oilNum)를 부여하고, BFS(큐 기반 너비 우선 탐색)로 연결된 모든 칸을 방문해 같은 ID를 isVisited[row][col]에 기록합니다.
   • BFS가 완료된 시점에 큐에서 꺼낸 횟수(count)가 해당 덩어리의 크기이므로, 이를 oilMap[oilNum]에 저장합니다.
   • 이렇게 하면 “각 덩어리 ID별 크기”가 oilMap에 저장되고, isVisited에는 “(row,col)에 속한 덩어리 ID”가 기록됩니다.
2. 열별 덩어리 합산
   • 모든 덩어리에 대해 ID와 크기를 구했으면, 이제 각 열(column)을 하나씩 선택하며 “그 열이 통과하는 덩어리 ID를 찾아 합산”해야 합니다.
   • isVisited[row][col]을 위에서부터 아래로 확인하면서, “만약 id = isVisited[row][col]가 0이 아니고, 해당 열에서 아직 더하지 않은 ID라면”
     • result += oilMap[id]
     • lastSeen[id] = col + 1로 “이 덩어리 ID가 이 열에서 이미 더해졌다”고 표시
   • 이렇게 하면 한 덩어리가 여러 칸으로 같은 열을 통과해도, lastSeen[id]를 통해 중복 합산을 방지하며 한 번만 더하게 됩니다.
   • 각 열의 합산 결과를 비교해 최댓값을 answer에 기록합니다.
3. 시간 복잡도
   • BFS 레이블링: 격자 전체를 한 번 훑어가며, 각 칸을 큐에서 한 번만 꺼내고 주변 4방향을 검사하므로 O(n×m)O(n \times m)O(n×m).
   • 열별 합산: mmm개의 열마다 위에서부터 아래로 최대 nnn칸만 검토하므로 O(n×m)O(n \times m)O(n×m).
   • 따라서 전체 복잡도는 O(n×m)O(n \times m)O(n×m)으로, n,m≤500n,m \le 500n,m≤500일 때 10초 제한 내에 충분히 처리 가능합니다.

---

전체 코드

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

class Solution {
    // lastSeen[id] = 마지막으로 id번 덩어리를 합산한 열 번호(1-based)  
    private int[] lastSeen;

    public int solution(int[][] land) {
        int n = land.length;
        int m = land[0].length;
        int maxCells = n * m;

        // isVisited[row][col] = 해당 칸이 속한 덩어리 ID
        int[][] isVisited = new int[n][m];
        // oilMap[id] = id번 덩어리의 크기(칸 개수)
        long[] oilMap = new long[maxCells + 1];
        // lastSeen[id]를 통해 열별 중복 합산을 방지
        lastSeen = new int[maxCells + 1];

        // 1) BFS로 한 번만 레이블링하여 덩어리 ID와 크기를 isVisited/oilMap에 기록
        setOilMap(land, oilMap, isVisited);

        // 2) 각 열별로 “해당 열이 통과하는 덩어리의 크기” 합산
        int answer = 0;
        for (int col = 0; col < m; col++) {
            int curOil = getOil(isVisited, oilMap, col, land);
            if (answer < curOil) {
                answer = curOil;
            }
        }
        return answer;
    }

    // 한 열(column)을 선택했을 때 뽑을 수 있는 기름량 계산
    private int getOil(int[][] isVisited, long[] oilMap, int col, int[][] land) {
        int result = 0;
        int n = land.length;

        for (int row = 0; row < n; row++) {
            int oilNum = isVisited[row][col];
            // 아직 더하지 않은 덩어리 ID라면 결과에 더하고 “이 열에서 이미 더했다”고 표시
            if (oilNum != 0 && lastSeen[oilNum] != col + 1) {
                result += oilMap[oilNum];
                lastSeen[oilNum] = col + 1;
            }
        }
        return result;
    }

    // BFS를 이용해 연결된 석유 덩어리를 찾아 ID 부여 및 크기 계산
    private void setOilMap(int[][] land, long[] oilMap, int[][] isVisited) {
        int n = land.length;
        int m = land[0].length;
        int oilNum = 1;  // 덩어리 ID는 1부터 시작

        // 4방향 델타
        int[] dx = { -1, 0, 1, 0 };
        int[] dy = {  0, -1, 0, 1 };
        Queue<int[]> queue = new ArrayDeque<>();

        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++) {
                // land[row][col] == 1이고, 아직 방문되지 않았다면 새 덩어리 시작
                if (land[row][col] == 1 && isVisited[row][col] == 0) {
                    isVisited[row][col] = oilNum;
                    queue.offer(new int[] { row, col });
                    int count = 0;

                    // BFS로 연결된 모든 칸 방문
                    while (!queue.isEmpty()) {
                        int[] cur = queue.poll();
                        count++;
                        int x = cur[0], y = cur[1];

                        for (int i = 0; i < 4; i++) {
                            int nx = x + dx[i];
                            int ny = y + dy[i];
                            if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
                                continue;
                            }
                            // land[nx][ny] == 1이고 아직 ID가 없다면 같은 덩어리로 표시하고 큐에 추가
                            if (land[nx][ny] == 1 && isVisited[nx][ny] == 0) {
                                isVisited[nx][ny] = oilNum;
                                queue.offer(new int[] { nx, ny });
                            }
                        }
                    }

                    // BFS가 끝난 뒤 count가 “oilNum번 덩어리의 크기”
                    oilMap[oilNum] = count;
                    oilNum++;
                }
            }
        }
    }

    // (사용하지 않아도 되지만, 참조를 위해 남겨둠)
    private boolean isOil(int[][] land, int[][] isVisited, int x, int y) {
        int n = land.length;
        int m = land[0].length;
        if (x < 0 || y < 0 || x >= n || y >= m || isVisited[x][y] != 0 || land[x][y] == 0) {
            return false;
        }
        return true;
    }
}