프로그래머스 석유 시추 자바 풀이

문제 링크

문제 풀이 시간 : 30분

문제 요약

1은 석유가 있는 칸, 0은 빈 땅
상하좌우로 연결된 1들은 하나의 석유 덩어리
시추관은 한 열 전체를 수직으로 관통
어떤 열이 석유 덩어리의 일부라도 지나면, 그 덩어리 전체를 획득
한 열에서 얻을 수 있는 석유량의 최댓값을 구하는 문제

문제 풀이

처음 보면 각 열마다 시추관을 하나씩 꽂아보고, 그 열에서 만나는 석유들을 탐색해서 합을 구하면 될 것처럼 보인다.

하지만 그렇게 하면 열마다 BFS/DFS를 반복하게 되고, 같은 석유 덩어리를 여러 번 다시 세게 된다.

n, m이 최대 500이기 때문에 이런 방식은 비효율적이다.

이 문제의 핵심은 석유 덩어리를 먼저 한 번만 구해두고, 그 덩어리가 어떤 열들에 걸쳐 있는지만 기록하는 것이다.

즉, 풀이 흐름은 다음과 같다.

아직 방문하지 않은 석유 칸을 만나면 BFS로 하나의 덩어리 전체를 탐색
그 덩어리의 크기(size) 를 구한다
그 덩어리가 포함된 열 번호들만 따로 모은다
이후 그 덩어리가 걸쳐 있는 모든 열에 대해 size를 더해준다

이때 중요한 점은, 같은 덩어리 안에서 어떤 열이 여러 번 등장할 수 있다는 것이다.

예를 들어 같은 덩어리의 칸이 한 열에 여러 개 있더라도, 그 열에서는 그 덩어리를 한 번만 더해야 한다.

그래서 BFS를 하면서 해당 덩어리가 포함된 열들을 Set<Integer>에 저장한다.

탐색이 끝나면

덩어리 크기 size
이 덩어리가 걸쳐 있는 열들 set

이 두 정보를 이용해서

sum[col] += size

형태로 누적하면 된다.

결국 sum[i]는 i번 열에 시추관을 설치했을 때 얻을 수 있는 총 석유량이 된다.

마지막에는 sum 배열의 최댓값만 구하면 정답이다.

풀이가 효율적인 이유

각 칸은 BFS에서 최대 한 번만 방문한다.

또한 각 덩어리에 대해 걸쳐 있는 열만 한 번씩 처리하므로 전체 시간 복잡도는 거의 O(n*m) 수준이다.

제한이 500 x 500이어도 충분히 통과 가능하다.

최종 코드

java

import java.util.*;

class Solution {
    public int solution(int[][] land) {
        int answer = 0;
        int n = land.length;
        int m = land[0].length;
        int[] sum = new int[m]; // 각 열에서 얻을 수 있는 석유 총합

        int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
        boolean[][] visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 이미 방문했거나 빈 땅이면 스킵
                if (visited[i][j] || land[i][j] == 0)
                    continue;

                Queue<int[]> q = new ArrayDeque<>();
                Set<Integer> set = new HashSet<>(); // 현재 덩어리가 걸쳐 있는 열들

                q.add(new int[]{i, j});
                visited[i][j] = true;

                int size = 0; // 현재 석유 덩어리 크기

                while (!q.isEmpty()) {
                    int[] now = q.poll();
                    size++;
                    set.add(now[1]); // 이 덩어리가 포함된 열 기록

                    for (int d = 0; d < 4; d++) {
                        int tx = now[0] + dir[d][0];
                        int ty = now[1] + dir[d][1];

                        // 범위를 벗어나거나, 이미 방문했거나, 빈 땅이면 스킵
                        if (tx < 0 || tx >= n || ty < 0 || ty >= m || visited[tx][ty] || land[tx][ty] == 0)
                            continue;

                        visited[tx][ty] = true;
                        q.add(new int[]{tx, ty});
                    }
                }

                // 현재 덩어리가 걸쳐 있는 모든 열에 덩어리 크기 더하기
                for (int next : set)
                    sum[next] += size;
            }
        }

        // 가장 많은 석유를 얻을 수 있는 열 찾기
        for (int i = 0; i < m; i++) {
            answer = Math.max(answer, sum[i]);
        }

        return answer;
    }
}

석유 시추

문제 풀이 시간 : 30분

문제 요약

문제 풀이

풀이가 효율적인 이유

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기