프로그래머스 | Level 2 | 석유 시추

Nov 03, 2024

Published byJynn

999

Programmers | Level 2 | 석유 시추

Problems

📘 Src: Programmers
🗂️ Cat: Breadth-First Search

󰧭 Description

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

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

시추관의 위치	획득한 덩어리	총 석유량
1	`[8]`	8
2	`[8]`	8
3	`[8]`	8
4	`[7]`	7
5	`[7]`	7
6	`[7]`	7
7	`[7,2]`	9
8	`[2]`	2

오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

 Constraints

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

효율성 테스트 케이스 제한사항

주어진 조건 외 추가 제한사항 없습니다.

󰦕 Examples

land	result
`[[0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 1]]`	9
`[[1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]]`	16

Solutions

󰘦 Code

Solution.java

import java.util.*;

class Solution {
    private static final int[] dx = {1, 0, -1, 0};  // 상하좌우 이동을 위한 x축 델타 배열
    private static final int[] dy = {0, 1, 0, -1};  // 상하좌우 이동을 위한 y축 델타 배열

    public int solution(int[][] land) {
        int n = land.length;
        int m = land[0].length;
        int[][] clusters = new int[n][m];       // 각 위치의 석유 덩어리 ID 저장
        boolean[][] marked = new boolean[n][m]; // 위치 방문 여부 확인 배열
        Map<Integer, Integer> volumes = new HashMap<>();  // 석유 덩어리 ID별 크기 저장
        int clusterId = 1;  // 석유 덩어리에 부여할 고유 ID
        
        // BFS를 통해 각 석유 덩어리를 탐색하고 크기 계산
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 아직 방문하지 않은 석유 위치에 대해 BFS 탐색
                if (land[i][j] == 1 && !marked[i][j]) {
                    int volume = bfs(i, j, clusterId, clusters, marked, n, m, land);
                    volumes.put(clusterId, volume);  // 덩어리 ID에 해당하는 크기 저장
                    clusterId++;  // 다음 덩어리를 위해 ID 증가
                }
            }
        }
        
        int maxVolume = Integer.MIN_VALUE;  // 최대 석유량 초기화
        // 각 열에 대해 시추관을 설치하고 해당 열의 석유량 계산
        for (int i = 0; i < m; i++) {
            Set<Integer> uniques = new HashSet<>();  // 현재 열에서 만난 고유 석유 덩어리 ID 저장
            int currVolume = 0;
            for (int j = 0; j < n; j++) {
                clusterId = clusters[j][i];
                // 덩어리가 존재하고 중복되지 않는 경우만 석유량 합산
                if (clusterId != 0 && uniques.add(clusterId)) {
                    currVolume += volumes.get(clusterId);  // 해당 덩어리 크기 누적
                }
            }
            maxVolume = Math.max(maxVolume, currVolume);  // 최대 석유량 갱신
        }
        
        return maxVolume;
    }
    
    // BFS를 통해 석유 덩어리를 탐색하고 크기를 계산하는 함수
    private int bfs(int row, int col, int clusterId, int[][] clusters, boolean [][] marked, int n, int m, int[][] land) {
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{row, col});
        marked[row][col] = true;  // 시작 위치 방문 처리
        clusters[row][col] = clusterId;  // 해당 위치에 클러스터 ID 할당
        
        int vol = 1;  // 현재 석유 덩어리의 크기 초기화
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int cx = curr[0];
            int cy = curr[1];
            
            // 상하좌우 인접 위치를 탐색하여 같은 덩어리인 경우 추가
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + cx;
                int ny = dy[i] + cy;
                // 유효한 위치이고 석유가 있으며 아직 방문하지 않은 경우
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !marked[nx][ny] && land[nx][ny] == 1) {
                    marked[nx][ny] = true;  // 방문 처리
                    clusters[nx][ny] = clusterId;  // 해당 위치에 클러스터 ID 할당
                    queue.offer(new int[]{nx, ny});  // 큐에 추가하여 탐색 확장
                    vol++;  // 덩어리 크기 증가
                }
            }
        }
        
        return vol;  // 현재 덩어리의 크기 반환
    }
}

 Approaches

이 문제는 그래프 탐색 유형으로, 효율적인 덩어리 탐색과 최대값을 찾는 알고리즘 설계가 요구됩니다. 탐색을 통해 연결된 영역의 크기를 구하고, 특정 조건에 따라 값들을 합산하여 최적의 결과를 도출하는 방식입니다.

1. 문제 분석

이 문제는 주어진 땅 속에서 최대한 많은 석유를 뽑아낼 수 있는 최적의 시추관 설치 위치를 찾는 것입니다. 땅 속의 석유는 여러 덩어리로 분리되어 있으며, 각 덩어리는 상하좌우로 연결된 1의 값들로 구성됩니다.

시추관은 특정 열에 수직으로 설치되어야 하며, 해당 열을 관통하는 모든 석유 덩어리의 크기를 합산하여 해당 위치에서 뽑아낼 수 있는 총 석유량을 구할 수 있습니다. 이를 통해 땅의 특정 열에 시추관을 설치했을 때 최대 석유량을 뽑아낼 수 있는 위치를 결정하게 됩니다.

그래프 탐색 기법을 활용하여 각 석유 덩어리의 크기를 계산하는 것이 이 문제의 첫 번째 주요 과제입니다. 이때 BFS를 사용하여 상하좌우로 연결된 석유 덩어리를 빠르게 탐색하고, 각 덩어리의 크기를 누적하여 기록해 두어야 합니다. 이렇게 계산한 덩어리의 크기 정보는 이후 각 열을 탐색할 때 활용됩니다.

그다음 각 열에 대해 시추관이 통과할 때 해당 열이 지나는 석유 덩어리들의 크기를 합산합니다. 이 과정에서 동일한 석유 덩어리가 여러 번 합산되지 않도록 집합을 사용해 중복을 방지합니다. 최종적으로, 각 열의 총 석유량 중에서 최대값을 찾아내어 최적의 시추 위치와 최대 석유량을 결정할 수 있습니다.

이와 같이 그래프 탐색을 통해 각 덩어리를 파악하고, 열별로 시추관 설치 시 얻을 수 있는 석유량을 계산함으로써 문제의 최적 해답을 도출하게 됩니다.

2. 접근 방식

가장 많은 석유량을 얻기 위해 다음 단계로 문제를 해결합니다.

석유 덩어리 탐색 및 크기 계산: 격자의 각 위치에서 석유가 있는지 확인하고, 석유가 있다면 BFS로 해당 위치와 연결된 석유 덩어리를 탐색합니다. BFS를 통해 각 석유 덩어리에 고유 ID를 부여하고, 덩어리의 크기를 계산해 해시맵에 저장합니다. 이를 통해 각 덩어리의 크기를 빠르게 조회하여 이후 열별 석유량 계산에 활용합니다.
시추관 설치 및 최대 석유량 추적: 각 열을 확인하며, 시추관이 지나가는 동안 만나는 석유 덩어리의 ID를 기록하고, 동일한 덩어리는 중복 계산하지 않도록 처리합니다. 열별로 시추관이 지나는 덩어리 크기를 누적하여 총 석유량을 계산하고, 이 중 최대값을 기록하여 반환합니다.

3. 방향 델타 및 초기 변수 설정

BFS 탐색을 통해 각 위치에서 상하좌우를 확인할 수 있도록 방향 델타 배열을 설정합니다. 또한 격자의 행과 열 크기를 구해 각 위치의 방문 여부와 덩어리 ID를 기록할 배열을 초기화하고, 덩어리의 크기를 저장할 해시맵과 ID를 관리할 변수를 준비합니다.

Solution.java

int[] dx = {1, 0, -1, 0};  // 상하좌우 이동을 위한 x축 델타 배열
int[] dy = {0, 1, 0, -1};  // 상하좌우 이동을 위한 y축 델타 배열
int n = land.length;       // 격자의 세로 길이
int m = land[0].length;    // 격자의 가로 길이
int[][] clusters = new int[n][m];  // 각 위치의 덩어리 ID를 저장하는 배열
boolean[][] marked = new boolean[n][m];  // 방문 여부를 기록하는 배열
Map<Integer, Integer> volumes = new HashMap<>();  // 덩어리 ID와 크기를 매핑하는 해시맵
int clusterId = 1;  // 덩어리 ID를 관리하는 변수

4. BFS를 통한 석유 덩어리 탐색 및 클러스터 ID 부여

BFS를 사용하여 석유가 있는 각 위치에서 해당 덩어리를 탐색하고, 연결된 모든 석유 칸을 하나의 덩어리로 묶어 클러스터 ID를 부여합니다. 이때, 방문한 위치를 표시하여 중복 탐색을 방지하고, 각 덩어리의 크기를 누적하여 계산합니다. 계산된 덩어리 크기는 클러스터 ID를 키로 하는 해시맵에 저장하여 이후 시추관 설치 시 빠르게 참조할 수 있습니다.

격자 내 각 위치 탐색: 격자의 각 칸을 순회하며 석유가 있는 위치(1로 표시된 위치)를 찾습니다. 석유가 있고 아직 방문하지 않은 위치에 대해서는 BFS를 통해 해당 위치와 연결된 석유 덩어리를 탐색합니다.
BFS 수행 및 클러스터 ID 할당: BFS를 시작하여 상하좌우로 연결된 석유 위치를 탐색하고, 각 위치에 같은 클러스터 ID를 할당합니다. 큐를 사용해 방문할 위치를 관리하며, 각 위치를 방문할 때마다 덩어리 크기를 1씩 증가시켜 해당 덩어리의 총 크기를 계산합니다.
덩어리 크기 저장: BFS 탐색이 완료되면, 계산된 덩어리의 크기를 해당 클러스터 ID와 함께 해시맵에 저장하여, 각 열의 시추관 설치 시 참조할 수 있도록 합니다.

이 과정을 통해 석유가 묻혀 있는 위치를 탐색하고, 각 덩어리의 크기를 관리할 수 있습니다.

Solution.java

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        // 석유가 있는 위치이고 아직 방문하지 않은 경우
        if (land[i][j] == 1 && !marked[i][j]) {
            int volume = bfs(i, j, clusterId, clusters, marked, n, m, land);  // BFS로 덩어리 탐색 및 크기 계산
            volumes.put(clusterId, volume);  // 클러스터 ID와 덩어리 크기 저장
            clusterId++;  // 다음 덩어리를 위한 ID 증가
        }
    }
}

BFS 탐색 함수는 다음과 같이 구성됩니다. 큐를 사용해 석유 덩어리를 탐색하며, 방문 위치와 클러스터 ID를 갱신하고 덩어리 크기를 누적합니다.

Solution.java

private int bfs(
        int row, 
        int col, 
        int clusterId, 
        int[][] clusters, 
        boolean [][] marked, 
        int n, 
        int m, 
        int[][] land
) {
    Deque<int[]> queue = new ArrayDeque<>();
    queue.offer(new int[]{row, col});
    marked[row][col] = true;  // 시작 위치 방문 처리
    clusters[row][col] = clusterId;  // 클러스터 ID 할당
    
    int vol = 1;  // 현재 덩어리의 초기 크기 설정
    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int cx = curr[0];
        int cy = curr[1];
        
        // 상하좌우로 연결된 위치 탐색
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + cx;
            int ny = dy[i] + cy;
            // 좌표가 유효하고, 석유가 있으며, 아직 방문하지 않은 위치일 경우
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !marked[nx][ny] && land[nx][ny] == 1) {
                marked[nx][ny] = true;  // 방문 표시
                clusters[nx][ny] = clusterId;  // 클러스터 ID 할당
                queue.offer(new int[]{nx, ny});  // 큐에 추가하여 BFS 탐색 이어감
                vol++;  // 덩어리 크기 증가
            }
        }
    }
    
    return vol;  // 현재 덩어리의 총 크기 반환
}

이 과정에서 탐색된 각 석유 덩어리는 고유한 클러스터 ID를 가지며, 덩어리의 크기는 해시맵에 기록되어 이후 시추관 설치 시 쉽게 참조할 수 있습니다.

5. 시추관 설치 및 최대 석유량 계산

각 열에 시추관을 설치하여 해당 열을 통과하는 모든 석유 덩어리의 크기를 합산해 석유량을 계산합니다. 이때, 동일한 덩어리가 여러 행에 걸쳐 있을 수 있으므로, 각 열에서 이미 계산한 덩어리를 중복 합산하지 않도록 관리합니다. 이렇게 계산한 각 열의 석유량 중 최대값을 갱신하여 최종적으로 가장 많은 석유량을 구할 수 있습니다.

열별 시추관 설치 및 중복 방지: 각 열을 순차적으로 탐색하면서, 시추관이 지나가는 위치의 석유 덩어리 ID를 확인하고, 해당 ID가 집합에 없을 경우에만 석유량을 합산합니다. 이렇게 하면 중복된 석유 덩어리의 합산을 방지할 수 있습니다.
최대 석유량 갱신: 각 열의 석유량을 계산한 후, 현재 최대 석유량과 비교하여 더 큰 값으로 갱신합니다.

Solution.java

int maxVolume = Integer.MIN_VALUE;  // 최대 석유량 초기화

// 각 열에 대해 시추관을 설치하고 석유량 계산
for (int i = 0; i < m; i++) {
    Set<Integer> uniques = new HashSet<>();  // 중복 방지를 위한 고유 ID 집합
    int currVolume = 0;
    for (int j = 0; j < n; j++) {
        clusterId = clusters[j][i];
        // 고유 ID가 중복되지 않을 경우만 합산
        if (clusterId != 0 && uniques.add(clusterId)) currVolume += volumes.get(clusterId);
    }
    maxVolume = Math.max(maxVolume, currVolume);  // 최대 석유량 갱신
}

6. 최대 석유량 반환

모든 열을 탐색하여 각 열의 최대 석유량을 계산한 후, 최종적으로 가장 큰 석유량을 반환하여 시추관을 설치할 최적의 열에서 얻을 수 있는 최대 석유량을 제공합니다.

Solution.java

// 최대 석유량 반환
return maxVolume;

󰄉 Complexity

⏳ TC: O(n × m)
💾 SC: O(n × m)

격자 내 모든 위치를 탐색해 석유 덩어리를 찾고, 각 열에 시추관을 설치하여 석유량을 계산하는 과정에서 O(n × m)의 시간 복잡도를 가집니다. 석유 덩어리와 각 위치의 클러스터 ID를 기록하기 위해 O(n × m)의 공간이 필요합니다.

Algorithm
BFS