프로그래머스 Lv.2 석유 시추

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

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

세로길이가 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 함수를 완성해 주세요.

제한사항

• 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 알고리즘을 통해 서로 연결된 석유 덩어리들을 확인하면서 석유 덩어리의 열 위치를 저장해 줍니다. 해당 석유 덩어리 집합이 추출될 수 있는 시추관의 위치와 동일하기 때문입니다. 주의할 점은 같은 열에 있는 석유 덩어리들은 같은 위치의 시추관에 의해 추출되기 때문에 중복 저장을 피하기 위해 Set 자료형에 시추관의 위치에 저장하였습니다.

마지막으로 각 석유 덩어리 집합의 석유 덩어리 개수를 확인할 때마다 시추관 위치별 석유 덩어리 집합의 개수를 계속해서 추가해 주어 가장 많은 석유량을 구했습니다.

풀이

import java.util.*;

class Solution {
    // 가로, 세로 길이
    static int n, m;
    // 시추관 위치별 석유량 
    static int[] oil;

    public int solution(int[][] land) {
        int answer = 0;

        n = land.length;
        m = land[0].length;
        oil = new int[m];

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

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (land[i][j] == 1 && visited[i][j] == false) {
                    bfs(land, visited, i, j);
                }
            }
        }

        answer = Arrays.stream(oil).max().getAsInt();
        System.out.println(answer);
        return answer;
    }

    public void bfs(int[][] land, boolean[][] visited, int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        visited[x][y] = true;

        // 상, 하, 좌, 우 이동
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        // 석유 덩어리 개수
        int count = 1;
        // 석유 덩어리의 열 위치 저장
        Set<Integer> set = new HashSet<>();

        while (!q.isEmpty()) {
            int[] now = q.poll();
            set.add(now[1]);

            for (int i = 0; i < 4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];

                // 땅 범위를 넘는 경우 생략
                if (!checkRange(nx, ny)) {
                    continue;
                }

                // 빈 땅이거나, 방문한 적이 있는 경우
                if (land[nx][ny] == 1 && visited[nx][ny] == false) {
                    q.add(new int[]{nx, ny});
                    visited[nx][ny] = true;
                    count += 1;
                }
            }
        }

        for (int index : set) {
            oil[index] += count;
        }
    }

    public boolean checkRange(int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m) {
            return false;
        }
        return true;
    }
}

결과