[프로그래머스 Lv.2] 석유 시추(Java) - BFS

📌 핵심 요약

• 열마다 BFS를 돌리면 안 된다 — 격자를 딱 한 번만 순회하며 석유 덩어리를 식별하는 것이 핵심이다
• 덩어리가 걸친 열을 Set으로 수집 — 같은 덩어리가 한 열에 여러 칸 걸쳐도 크기는 한 번만 더해야 한다
• 결산을 BFS 안에서 끝낸다 — 덩어리를 찾은 자리에서 걸친 열에 크기를 누적하면 중간 자료구조가 필요 없다
• 시간 복잡도 O(n×m) — 각 칸은 정확히 한 번만 큐에 들어간다

 

목차

1 문제 정리

Programmers #250136

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

1 ≤ land 행 ≤ 500 · 1 ≤ land 열 ≤ 500

난이도: Lv.2

n × m 격자로 표현된 땅이 주어진다. 값이 1인 칸에는 석유가 있고, 상하좌우로 인접한 1들은 하나의 석유 덩어리를 이룬다. 시추관을 세로로 하나 박으면, 그 관이 지나가는 칸에 조금이라도 걸친 덩어리는 통째로 채굴된다. 얻을 수 있는 석유량의 최댓값을 구하는 문제다.

문제의 핵심

1. 시추관은 세로 방향이므로, 선택 후보는 열 단위다
2. 덩어리는 일부만 걸쳐도 전체가 채굴되므로, 덩어리마다 크기와 걸친 열을 알아야 한다
3. 한 덩어리가 같은 열에 여러 칸 걸쳐도 크기는 한 번만 더해야 한다

2 처음 접근이 실패한 이유

처음에는 “열마다 시추관을 박아보고, 그 자리에서 BFS로 석유를 세면 되겠다”라고 생각했다. 열 0에 박고 BFS, 열 1에 박고 BFS, 이런 식으로 반복하는 구조였다.

이 접근에는 두 가지 문제가 있었다.

중복 탐색으로 인한 시간 초과

격자가 최대 500 × 500 = 250,000칸이고 열이 최대 500개다. 열마다 탐색을 새로 돌리면 같은 덩어리를 수백 번 다시 훑게 된다. 게다가 매번 visited 배열을 새로 할당하는 비용까지 붙는다.

순회 로직이 BFS 큐에 섞여 들어간 것

“다음 열로 넘어가기”, “다음 행으로 넘어가기” 같은 격자 순회 로직을 BFS 큐 안에 넣으려다 코드가 무너졌다. BFS 큐는 하나의 덩어리를 퍼뜨리는 상태만 담아야 하고, 격자 순회는 바깥 이중 for문이 담당해야 한다는 것을 놓쳤다.

⚠️

큐에 담을 값의 기준

초기 코드에서는 큐에 {x, y, count}를 담았다. 하지만 덩어리 크기는 특정 칸의 속성이 아니라 탐색 전체에 하나뿐인 결과값이다. 노드마다 달라지는 값만 큐에 담고, 전체에 속하는 값은 큐 바깥에서 누적해야 한다.

3 풀이 전략

발상을 뒤집었다. 열 입장에서 덩어리를 찾는 것이 아니라, 덩어리 입장에서 걸친 열을 기록하는 것이다.

전체 흐름

1. 격자를 처음부터 끝까지 순회하며 아직 방문하지 않은 석유 칸을 찾는다
2. 발견하면 BFS로 연결된 칸을 전부 탐색하며 덩어리 크기를 센다
3. 동시에 그 덩어리가 걸친 열 번호를 Set에 모은다
4. 탐색이 끝나면 Set에 모인 각 열에 덩어리 크기를 누적한다
5. 모든 덩어리를 처리한 뒤 열별 누적값 중 최댓값을 반환한다

Set이 필요한 이유

아래처럼 덩어리가 세로로 길쭉하면 한 열에 세 칸이 걸친다.

   

example — 세로로 걸친 덩어리

// 0번 열에 시추관을 박는 경우
1 0 0
1 0 0   → 같은 덩어리(크기 3)가 0번 열에 3칸 걸침
1 0 0   → 채굴량은 3이지 9가 아니다

칸을 만날 때마다 크기를 더하면 3을 세 번 더해 9가 된다. Set<Integer> columns에 열 번호를 모으면 중복이 자동으로 제거되므로, 이 실수가 자료구조 차원에서 막힌다.

🚨

예제는 통과하고 제출은 틀리는 케이스

예제 입력에서는 덩어리가 한 열에 한 칸씩만 걸치는 경우가 많아 중복 제거를 빼먹어도 정답이 나온다. 실제 채점 데이터에서 세로로 긴 덩어리를 만나면 그때 틀린다.

4 전체 코드

   

Java — Solution.java

import java.util.*;

class Solution {
    // 상, 하, 좌, 우
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    static int n, m;
    static boolean[][] visited;
    static int[] oilPerColumn; // 열별 누적 채굴량

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

        visited = new boolean[n][m];
        oilPerColumn = new int[m];

        // 격자 전체를 한 번 순회하며 석유 덩어리를 찾는다
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (land[r][c] == 1 && !visited[r][c]) {
                    bfs(land, r, c);
                }
            }
        }

        int maxOil = 0;
        for (int oil : oilPerColumn) {
            maxOil = Math.max(maxOil, oil);
        }
        return maxOil;
    }

    private void bfs(int[][] land, int startR, int startC) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{startR, startC});
        visited[startR][startC] = true;

        int size = 0;                           // 덩어리 크기
        Set<Integer> columns = new HashSet<>(); // 덩어리가 걸친 열 번호

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0];
            int c = curr[1];

            size++;
            columns.add(c);

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (nr >= 0 && nr < n && nc >= 0 && nc < m
                        && land[nr][nc] == 1 && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        // 덩어리가 걸친 모든 열에 크기를 누적
        for (int col : columns) {
            oilPerColumn[col] += size;
        }
    }
}

5 코드 상세

방문 표시 시점

큐에 넣는 순간 visited를 true로 바꾼다. 꺼낼 때 표시하면 같은 칸이 여러 경로로 큐에 중복 삽입되어 size가 부풀려진다.

size를 큐에 담지 않는 이유

size는 BFS 하나에 하나뿐인 값이므로 큐가 아니라 메서드의 지역 변수로 둔다. 큐에는 칸마다 달라지는 좌표만 담는다. 이 구분이 초기 코드가 무너진 지점이었다.

ArrayDeque와 LinkedList

최대 250,000칸이 큐를 거쳐 간다. LinkedList는 원소마다 노드 객체를 새로 할당하므로 ArrayDeque를 쓰는 편이 낫다.

💡

타입이 같으면 컴파일러가 잡아주지 못한다

행 번호, 열 번호, 덩어리 번호가 전부 int다. 자리를 바꿔 넣어도 컴파일 에러가 나지 않으므로, 변수명을 역할에 맞게 붙이는 것이 실질적인 방어책이 된다.

6 복잡도와 정리

단계	동작	복잡도
덩어리 탐색	각 칸이 정확히 한 번만 큐에 진입	O(n×m)
열 누적	덩어리마다 걸친 열 수만큼 가산	O(n×m)
최댓값 탐색	열 배열 1회 순회	O(m)

전체 O(n×m)이며 최대 250,000회 수준이라 여유롭게 통과한다.

ℹ️

이 문제에서 남은 것

BFS 자체는 어렵지 않았다. 어려웠던 것은 “무엇을 기준으로 탐색할 것인가”를 정하는 부분이었다. 선택 후보(열)를 기준으로 탐색하려 하니 중복 계산이 생겼고, 탐색 대상(덩어리)을 기준으로 뒤집자 한 번의 순회로 정리됐다. 완전탐색처럼 보이는 문제에서 순회의 주체를 무엇으로 둘 것인가를 먼저 판단해야 한다는 점을 확인했다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.