[PCCP 기출문제] 2번 / 석유 시추

문제 설명

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

풀이

grid에서 각 island의 크기를 구한 뒤, 각 열(column)에서 관통하는 island 크기의 합의 최대치를 구하는 문제라고 볼 수 있다.

이때 각 island의 크기를 구하는 부분은 bfs 혹은 dfs로 풀 수 있으며, 추가적으로 각 island의 열 범위 (최소, 최대)를 트랙킹할 필요가 있다.

각 island의 열 범위와 크기를 얻은 뒤엔 해당 정보를 순회하면서 island 크기의 최대합을 구할 수 있다.

위 그림을 통해 살펴보면, 7번 열에서 크기가 7인 island와 크기가 2인 island를 관통하며 크기의 합이 9로 최대가 됨을 알 수 있다.

bfs를 통해 구하려는 정보는 아래와 같다.

1번 island : 최소 열 1, 최대 열 3, 크기 8
2번 island : 최소 열 4, 최대 열 7, 크기 7
3번 island : 최소 열 7, 최대 열 8, 크기 2

이제 코드를 살펴보자.

public int solution(int[][] lands) {
        List<int[]> islands = new ArrayList<>();
        int rows = lands.length;
        int cols = lands[0].length;
        boolean[][] visited = new boolean[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (lands[i][j] == 1 && !visited[i][j]) {
                    int[] islandInfo = bfs(lands, i, j, visited);
                    islands.add(islandInfo);
                }
            }
        }
        
        ...
}

우선은 bfs를 시작하며, island에 대한 정보를 저장하는 부분이다.

각 island의 최소/최대 열 그리고 크기 정보는 int 배열에 담는다.

방문한 cell을 구분하기 위해 visited 배열도 만들어준다.

다음은 실제로 bfs를 수행하는 부분이다.

private static int[] bfs(int[][] grid, int startRow, int startCol, boolean[][] visited) {
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        queue.offer(new int[]{startRow, startCol});
        visited[startRow][startCol] = true;
        
        int minColumn = Integer.MAX_VALUE;
        int maxColumn = Integer.MIN_VALUE;
        int size = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];

            minColumn = Math.min(col, minColumn);
            maxColumn = Math.max(col, maxColumn);
            size++;

            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols
                        && grid[newRow][newCol] == 1 && !visited[newRow][newCol]) {
                    queue.offer(new int[]{newRow, newCol});
                    visited[newRow][newCol] = true;
                }
            }
        }
        
        return new int[]{minColumn, maxColumn, size};
}

일반적인 bfs 코드와 크게 다르지 않으나, 최소/최대 열과 크기를 구하는 부분이 추가되었다.

크기의 경우, bfs 코드를 실행한다는 의미는 해당 cell을 최초로 방문한다는 의미이므로 무조건 크기를 하나 늘려준다. (size++)

마지막으로 모든 island 방문을 끝낸뒤, island 크기의 최대합을 구하는 부분이다.

int[] sums = new int[lands[0].length];
        
for (int[] island : islands) {
   for (int col = island[0]; col <= island[1]; col++) {
      sums[col] += island[2];
   }
}

return Arrays.stream(sums).max().getAsInt();

열의 크기만큼 배열을 하나 생성해주고 (sums), 각 열에 대해 도달 가능한 island의 크기를 더해주면 각 열에서 도달 가능한 island의 크기의 합계를 알 수 있다.

위 예시에서 sums는

1번 열: 8
2번 열: 8
3번 열: 8
4번 열: 7
5번 열: 7
6번 열: 7
7번 열: 9
8번 열: 2

가 되므로 정답은 9가 된다.

전체 코드는 아래와 같다.

import java.util.*;

class Solution {
    public int solution(int[][] lands) {
        List<int[]> islands = new ArrayList<>();
        int rows = lands.length;
        int cols = lands[0].length;
        boolean[][] visited = new boolean[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (lands[i][j] == 1 && !visited[i][j]) {
                    int[] islandInfo = bfs(lands, i, j, visited);
                    islands.add(islandInfo);
                }
            }
        }
        
        int[] sums = new int[lands[0].length];
        
        for (int[] island : islands) {
            for (int col = island[0]; col <= island[1]; col++) {
                sums[col] += island[2];
            }
        }
        
        return Arrays.stream(sums).max().getAsInt();
    }
    
    private static int[] bfs(int[][] grid, int startRow, int startCol, boolean[][] visited) {
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        queue.offer(new int[]{startRow, startCol});
        visited[startRow][startCol] = true;
        
        int minColumn = Integer.MAX_VALUE;
        int maxColumn = Integer.MIN_VALUE;
        int size = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];

            minColumn = Math.min(col, minColumn);
            maxColumn = Math.max(col, maxColumn);
            size++;

            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols
                        && grid[newRow][newCol] == 1 && !visited[newRow][newCol]) {
                    queue.offer(new int[]{newRow, newCol});
                    visited[newRow][newCol] = true;
                }
            }
        }
        
        return new int[]{minColumn, maxColumn, size};
    }
}

시간/공간 복잡도

시간 복잡도의 경우 크게 2파트로 나뉘는데, 첫번째 파트는 grid에 대해 bfs를 하는 부분으로 n x m grid에 대해 O(n m)이 된다. 두번째 파트는 sums 배열에 대해 최대합을 구하는 부분으로 O(m)이 되는데, 결국 grid에 대한 bfs 과정이 지배적이므로 최종적으로는 O(n m)이 된다.

공간 복잡도 역시 grid에 대한 bfs 부분이 지배적인데, visited 배열이 O(n m) 만큼의 공간을 추가적으로 사용하므로 공간 복잡도는 O(n m)이 된다.

시간 복잡도 : O(n * m)
공간 복잡도 : O(n * m)