링크

문제링크

문제

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

세로길이가 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
  효율성 테스트 케이스 제한사항
• 주어진 조건 외 추가 제한사항 없습니다.

입출력

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

해결

• 첫 번째 시도 코드
  처음엔 너비 우선 탐색 알고리즘을 활용하여
  가로 인덱스(m) 별로 땅을 파고 내려가면서 석유가 있을 시 그 주변을 모두 탐색한다.
  탐색하면서 석유 덩어리의 크기를 oil에 기록한다.
  이 코드는 가로 인덱스 별로 새로운 visitedLand를 복사하고 매번 그 인덱스에 걸치는 석유를 모두 탐사하기에 같은 석유 덩이를 반복하여 탐색하게 된다.
  그래서 효율성에서 점수를 받지 못하여 두번째 알고리즘을 시도하였다.

• 두 번째 시도 코드
  너비 우선 탐색 알고리즘인건 같지만 land를 탐색하면서 석유를 만나면 그 주변을 모두 탐색한다.
  탐색 할때 oilVolume oilIdxSet을 사용하여 만난 석유덩이의 크기, 그 석유덩이가 가로 인덱스를 어디를 걸치고 있는지 기록한다.
  그리고 석유 덩이 탐색이 모두끝나면 oil에 oilIdxSet를 참고하여 oilVolume을 더해준다.
  이렇게 하면 각 석유를 한 번만 탐색할 수 있다.

코드

첫 번째 시도 코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int[][] land) {
        int answer = 0;
        
        int[] oil = new int[land[0].length];
        int n = land.length;
        int m = land[0].length;

        oil = bfs(land, n, m);

        answer = Arrays.stream(oil).max().getAsInt();
        
        return answer;
    }
    
    private static int[] bfs(int[][] land, int n, int m) {
        int[] oil = new int[m];
        Queue<int[]> queue;
        int[] dRow = {1, 0, 0, -1};
        int[] dCol = {0, 1, -1, 0};

        for (int i = 0; i < m; i++) {
            int findOil = 0;
            int[][] visitedLand = new int[n][m];
            queue = new LinkedList<>();

            //land 깊은 복사
            for (int j = 0; j < visitedLand.length; j++) {
                visitedLand[j] = land[j].clone();
            }

            //현재 m 라인에서 석유가 있는지 체크하고 있다면 큐에 삽입
            for (int j = 0; j < n; j++) {

                if (visitedLand[j][i] == 1) {
                    queue.add(new int[]{j, i});
                    visitedLand[j][i] = 0;
                }
            }

            while (!queue.isEmpty()) {
                int[] curPos = queue.poll();
                int curRow = curPos[0];
                int curCol = curPos[1];

                findOil++;

                for (int j = 0; j < 4; j++) {
                    int nextRow = curRow + dRow[j];
                    int nextCol = curCol + dCol[j];
                    if (0 <= nextRow && nextRow < n && 0 <= nextCol && nextCol < m) {
                        if (visitedLand[nextRow][nextCol] == 1) {
                            visitedLand[nextRow][nextCol] = 0;
                            queue.add(new int[]{nextRow, nextCol});
                        }
                    }
                }

            }

            oil[i] = findOil;
        }

        return oil;
    }
}

• 정확성 테스트 만점
• 효율성 테스트 0점(시간초과)

두 번째 시도 코드

import java.util.*;

class Solution {
    public int solution(int[][] land) {
        int answer = 0;
        
        int[] oil;
        int n = land.length;
        int m = land[0].length;

        oil = searchOil(land, n, m);

        answer = Arrays.stream(oil).max().getAsInt();
        
        return answer;
    }
    
    private static int[] searchOil(int[][] land, int n, int m) {
        int[] oil = new int[m];
        Queue<int[]> queue;
        int[] dRow = {1, 0, 0, -1};
        int[] dCol = {0, 1, -1, 0};

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (land[i][j] == 1) {
                    queue = new LinkedList<>();
                    int oilVolume = 0;
                    Set<Integer> oilIdxSet = new HashSet<>();

                    queue.add(new int[]{i, j});

                    while (!queue.isEmpty()) {
                        int[] curPos = queue.poll();
                        int curRow = curPos[0];
                        int curCol = curPos[1];

                        land[curRow][curCol] = 0;
                        oilIdxSet.add(curCol);
                        oilVolume++;

                        for (int k = 0; k < 4; k++) {
                            int nextRow = curRow + dRow[k];
                            int nextCol = curCol + dCol[k];
                            if (0 <= nextRow && nextRow < n && 0 <= nextCol && nextCol < m) {
                                if (land[nextRow][nextCol] == 1) {
                                    land[nextRow][nextCol] = 0;
                                    queue.add(new int[]{nextRow, nextCol});
                                }
                            }
                        }
                    }

                    for (int cur : oilIdxSet) {
                        oil[cur] += oilVolume;
                    }

                }

            }
        }

        return oil;
    }
}