BFS (3) - 석유 시추

문제

---

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

 

조건

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

효율성 테스트 케이스 제한사항
주어진 조건 외 추가 제한사항 없습니다.

 

 

 

풀이

---

처음 문제를 보고, BFS가 생각났다. 각 부분별로 BFS를 이용하여 덩어리를 나누고, 해당 인덱스 배열에 덩어리의 크기를 저장하여 문제를 풀어보기로 하였다.

 

 

 

에러 핸들링

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

    static int n, m;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int[][] score; // scoreArr의 인덱스를 담을 배열
    static int[] scoreArr; // 각 시추기 숫자 별 석유 매장량 기록
    static int maxScore = Integer.MIN_VALUE;

    public static void bfs(int[][] land, int[] start) {
        int lScore = 1;
        ArrayDeque<int[]> dq = new ArrayDeque<>();
        dq.offer(start);
        score[start[0]][start[1]] = start[1] + 1;
        land[start[0]][start[1]] = 0;
        while (!dq.isEmpty()) {
            int[] cur = dq.poll();
            for (int i = 0; i < 4; i++) {
                int x = cur[1] + dx[i];
                int y = cur[0] + dy[i];
                if (y <= m && x <= n && x >= 0 && y >= 0 && land[y][x] == 1) {
                    dq.offer(new int[]{y, x});
                    score[y][x] = start[1] + 1;
                    land[y][x] = 0;
                    lScore++;
                }
            }
        }
        scoreArr[start[1]] += lScore;
    }

    public static int solution(int[][] land) {
        n = land[0].length - 1; // 가로
        m = land.length - 1; // 세로
        score = new int[m + 1][n + 1];
        scoreArr = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (land[j][i] == 1) {
                    bfs(land, new int[]{j, i});
                }
            }
        }

        for (int i = 0; i <= n; i++) {
            ArrayList<Integer> sumArr = new ArrayList<>();
            for (int j = 0; j <= m; j++) {
                if (score[j][i] > 0) {
                    if (!sumArr.contains(score[j][i])) {
                        sumArr.add(score[j][i]);
                    }
                }
            }
                int localScore = 0;
                for (Integer s : sumArr) {
                    localScore += scoreArr[s - 1];
                }
                maxScore = Math.max(maxScore, localScore);

        }
        System.out.println(maxScore);
        return maxScore;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        solution(new int[][]{{1,1,1,1,0},{1,0,0,0,0},{0,0,0,1,1},{1,0,0,1,0},{1,1,0,1,0}});
    }

}

 

처음 풀었을 때, 오류가 나던 코드다. 나의 경우에는 배열을 돌면서 점수판을 만들어 처음 시추기가 찾은 석유 덩어리마다 해당 인덱스로 score 배열에 저장해주었다. 하지만, 이 방법은 일부분만 연결된 인덱스가 생길 수 있어 반례가 있었다.

(예를 들어 1에 덩어리가 2개이고, 각각 5와 3으로, 합이 8이라고 가정했을 때, 해당 덩어리를 1번 인덱스에 8로 저장했으나, 다른 인덱스에서는 5에 해당하는 덩어리만 포함하는 경우)

그래서, 생각해낸 방법은, 인덱스가 아닌, 덩어리만의 고유 아이디를 기록하는 것이었다.

 

 

 

정답

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashSet;

class Solution {
    static int n, m;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int[][] score; // 덩어리 ID 저장 배열
    static int[] scoreArr; // 덩어리 ID별 석유 매장량 저장
    static int maxScore = Integer.MIN_VALUE;
    static int id = 1; // 덩어리 ID 시작값 (1부터 시작)

    public static void bfs(int[][] land, int startY, int startX) {
        int lScore = 1;
        ArrayDeque<int[]> dq = new ArrayDeque<>();
        dq.offer(new int[]{startY, startX});
        score[startY][startX] = id;
        land[startY][startX] = 0;

        while (!dq.isEmpty()) {
            int[] cur = dq.poll();
            for (int i = 0; i < 4; i++) {
                int x = cur[1] + dx[i];
                int y = cur[0] + dy[i];
                if (y >= 0 && y <= m && x >= 0 && x <= n && land[y][x] == 1) {
                    dq.offer(new int[]{y, x});
                    score[y][x] = id;  // 덩어리 ID 저장
                    land[y][x] = 0;
                    lScore++;
                }
            }
        }
        scoreArr[id] = lScore; // 덩어리 ID별 석유 매장량 저장
        id++; // 다음 덩어리를 위해 ID 증가
    }

    public static int solution(int[][] land) {
        n = land[0].length - 1; // 가로 길이
        m = land.length - 1;    // 세로 길이
        score = new int[m + 1][n + 1];
        scoreArr = new int[(m + 1) * (n + 1)]; // 최대 덩어리 수에 맞게 배열 크기 설정

        // BFS로 덩어리 탐색 및 석유 매장량 기록
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (land[i][j] == 1) {
                    bfs(land, i, j);
                }
            }
        }

        // 각 열에서 최대 석유 매장량 계산
        for (int col = 0; col <= n; col++) {
            HashSet<Integer> uniqueClusters = new HashSet<>(); // 중복 덩어리 방지
            int localScore = 0;

            for (int row = 0; row <= m; row++) {
                if (score[row][col] > 0) {
                    uniqueClusters.add(score[row][col]);
                }
            }

            for (int clusterId : uniqueClusters) {
                localScore += scoreArr[clusterId];
            }

            maxScore = Math.max(maxScore, localScore);
        }

        return maxScore;
    }
}

 

마지막에 각 시추기의 인덱스별로, 합을 갱신하여 최대 스코어를 반환해주면 된다.