[programmers/java] 석유 시추 – Union-Find, BFS

문제 요약

• url : https://school.programmers.co.kr/learn/courses/30/lessons/250136

가로 M, 세로 N의 격자 land가 주어지며, 1은 석유가 있는 칸, 0은 빈 칸이다. 상하좌우로 연결된 1은 하나의 석유 덩어리로 간주한다. 단 하나의 열(column)에만 시추관을 설치할 수 있고, 해당 열과 연결된 석유 덩어리들의 총 크기 합이 최대가 되도록 설치해야 한다.

---

방법 1. Union-Find 방식

개요

각 칸을 유니온 파인드로 연결하며 석유 덩어리를 그룹핑하고, 각 그룹의 크기를 기록한다. 시추관을 각 열마다 내릴 때 해당 열을 관통하는 덩어리들을 중복 없이 집계해 최대 석유량을 계산한다.

import java.util.*;

class Solution {
    int[] parent;
    int[] size;
    int N, M;

    public int solution(int[][] land) {
        N = land.length;
        M = land[0].length;
        int total = N * M;
        parent = new int[total];
        size = new int[total];

        // 초기화: 각 칸은 자기 자신을 부모로 가짐
        for (int i = 0; i < total; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        // 1. 유니온 파인드로 덩어리 병합
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!isOil(land, i, j)) continue;
                int id = toId(i, j);
                for (int[] dir : new int[][]{{0,1},{0,-1},{1,0},{-1,0}}) {
                    int ni = i + dir[0];
                    int nj = j + dir[1];
                    if (isOil(land, ni, nj)) {
                        union(id, toId(ni, nj));
                    }
                }
            }
        }

        // 2. 각 그룹의 크기 집계
        Map<Integer, Integer> groupOil = new HashMap<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!isOil(land, i, j)) continue;
                int root = find(toId(i, j));
                groupOil.put(root, groupOil.getOrDefault(root, 0) + 1);
            }
        }

        // 3. 열마다 시추 가능한 최대 석유량 계산
        int maxOil = 0;
        for (int j = 0; j < M; j++) {
            Set<Integer> seen = new HashSet<>();
            for (int i = 0; i < N; i++) {
                if (isOil(land, i, j)) {
                    seen.add(find(toId(i, j)));
                }
            }
            int sum = 0;
            for (int group : seen) sum += groupOil.get(group);
            maxOil = Math.max(maxOil, sum);
        }

        return maxOil;
    }

    private int toId(int x, int y) {
        return x * M + y;
    }

    private boolean isInBounds(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < M;
    }

    private boolean isOil(int[][] land, int x, int y) {
        return isInBounds(x, y) && land[x][y] == 1;
    }

    private int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    private void union(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return;
        if (size[ra] < size[rb]) {
            parent[ra] = rb;
            size[rb] += size[ra];
        } else {
            parent[rb] = ra;
            size[ra] += size[rb];
        }
    }
}

---

방법 2. BFS 방식

개요

각 1에서 BFS로 연결된 석유 덩어리를 순회하며 그룹 번호를 부여한다. 각 그룹의 크기를 저장하고, 열을 기준으로 덩어리 집합을 수집하여 최대 석유량을 구한다.

import java.util.*;

class Solution {
    int[][] groupMap = new int[501][501];
    int N, M;

    public int solution(int[][] land) {
        N = land.length;
        M = land[0].length;
        int groupId = 0;
        Map<Integer, Integer> groupSize = new HashMap<>();

        // 1. BFS로 그룹화
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (isOil(land, i, j) && groupMap[i][j] == 0) {
                    groupId++;
                    int count = bfs(land, i, j, groupId);
                    groupSize.put(groupId, count);
                }
            }
        }

        // 2. 열마다 통과하는 그룹들의 크기 합산
        int maxOil = 0;
        for (int j = 0; j < M; j++) {
            Set<Integer> seen = new HashSet<>();
            for (int i = 0; i < N; i++) {
                int group = groupMap[i][j];
                if (group > 0) seen.add(group);
            }
            int sum = 0;
            for (int g : seen) sum += groupSize.get(g);
            maxOil = Math.max(maxOil, sum);
        }

        return maxOil;
    }

    private int bfs(int[][] land, int x, int y, int groupId) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        groupMap[x][y] = groupId;
        int count = 0;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            count++;

            for (int[] d : new int[][]{{0,1},{0,-1},{1,0},{-1,0}}) {
                int nx = cur[0] + d[0];
                int ny = cur[1] + d[1];
                if (isOil(land, nx, ny) && groupMap[nx][ny] == 0) {
                    groupMap[nx][ny] = groupId;
                    q.offer(new int[]{nx, ny});
                }
            }
        }

        return count;
    }

    private boolean isInBounds(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < M;
    }

    private boolean isOil(int[][] land, int x, int y) {
        return isInBounds(x, y) && land[x][y] == 1;
    }
}

---

두 방식의 비교

항목	Union-Find	BFS
전략	덩어리를 병합하여 빠르게 그룹화	BFS로 각 덩어리를 순회하며 그룹화
시간 복잡도	O(N*M)	O(N*M)
구현 난이도	다소 복잡	직관적
공간 사용량	parent, size 사용	groupMap 사용
장점	연결성 판단에 강함	구조가 명확하고 이해 쉬움
단점	배열 관리 복잡	대형 입력 시 재귀 스택 유의 필요