프로그래머스 - PCCP 기출문제 - 석유 시추

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

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

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

---

입출력 예제

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

---

풀이

처음에는 column별로 각 column에서 석유칸이 나올 경우 해당 석유가 속한 크기를 bfs로 구하고 이를 더하는 방식으로 문제를 풀었고 정확성 테스트는 통과할 수 있었으나 효율성 테스트에서 시간 초과가 발생하였다.

생각을 해본 결과 column 별로 석유 덩어리의 크기를 구하는 것은 여러 column에서 동시에 발견되는 석유 덩어리들의 경우 이미 크기를 잰 석유 덩어리의 크기를 또 재야하는 문제가 발생하였기에 이번에는 크기를 잰 석유 덩어리에 번호를 매기고 그 크기와 함께 저장해두어 column 별로 자신의 column에 속한 석유 덩어리의 번호만 읽게 하여 해당 번호와 저장되어 있는 크기를 확인만 하면 되도록 코드를 개선하여 문제를 해결할 수 있었다.

---

오답 코드 - 효율성 테스트 시간 초과

import java.util.*;

class Solution {
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int answer = 0;
    public int solution(int[][] land) {        
        for(int i = 0; i < land[0].length; i++) {
            bfs(land, i);
        }
        
        return answer;
    }
    
    public static void bfs(int[][] land, int column) {
        int cnt = 0;
        boolean[][] visited = new boolean[land.length][land[0].length];
        Queue<point> q = new LinkedList<>();
        
        for(int i = 0; i < land.length; i++) {
            int x = i;
            int y = column;
            
            if(land[x][y] == 1 && !visited[x][y]) {
                q.offer(new point(x, y));
                visited[x][y] = true;
                
                while(!q.isEmpty()) {
                    cnt++;
                    point p = q.poll();
                    
                    int nowx = p.x;
                    int nowy = p.y;
                    
                    for(int j = 0; j < 4; j++) {
                        int nextx = p.x + dx[j];
                        int nexty = p.y + dy[j];
                        
                        if(nextx >= 0 && nextx < land.length && nexty >= 0 && nexty < land[0].length) {
                            if(land[nextx][nexty] == 1 && !visited[nextx][nexty]) {
                                q.offer(new point(nextx, nexty));
                                visited[nextx][nexty] = true;
                            }
                        }
                    }
                }
            }
        }
        answer = Math.max(answer, cnt);
    }
}

class point {
    int x, y;
    
    point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

정답 코드

import java.util.*;

class Solution {
    // 각 석유 덩어리의 번호와 그 양을 저장하는 HashMap, 각 석유 덩어리의 번호를 매겨 bfs의 체크 횟수를 줄임
    static HashMap<Integer, Integer> hm = new HashMap<>();
    static boolean[][] visited;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    public int solution(int[][] land) {
        // 석유 덩어리의 번호를 매기는 num, land가 0과 1로 이루어져 있기에 덩어리 번호는 2번부터 시작
        int num = 2;
        visited = new boolean[land.length][land[0].length];
        
        // land를 확인하며 각 석유 덩어리의 크기를 bfs로 구하고 이를 HashMap에 저장
        for(int i = 0; i < land.length; i++) {
            for(int j = 0; j < land[0].length; j++) {
                if(land[i][j] == 1 && !visited[i][j]) {
                    land = bfs(land, i, j, num++);
                }
            }
        }
        
        int answer = 0;
        
        // column 별로 시추를 하면서 해당 column에 속한 석유 덩어리들의 번호를 HashSet에 저장해 중복을 제거하고
        // HashSet에 저장된 석유 번호들에 해당하는 크기를 HashMap에서 읽어와 sum을 구하고 answer와 크기 비교
        for(int i = 0; i < land[0].length; i++) {
            HashSet<Integer> hs = new HashSet<>();
            int sum = 0;
            
            for(int j = 0; j < land.length; j++) {
                if(land[j][i] != 0) {
                    hs.add(land[j][i]);
                }
            }
            
            for(Integer chunk : hs) {
                sum += hm.get(chunk);
            }
            
            answer = Math.max(answer, sum);
        }
        
        return answer;
    }
    
    // 각 석유 덩어리의 크기를 구하고 번호를 매겨 저장하는 bfs 함수
    public static int[][] bfs(int[][] land, int x, int y, int num) {
        int cnt = 0;
        Queue<point> q = new LinkedList<>();
        q.offer(new point(x, y));
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            cnt++;
            point p = q.poll();
            land[p.x][p.y] = num;
            
            for(int i = 0; i < 4; i++) {
                int nowX = p.x + dx[i];
                int nowY = p.y + dy[i];
                
                if(nowX >= 0 && nowX < land.length && nowY >= 0 && nowY < land[0].length) {
                    if(land[nowX][nowY] == 1 && !visited[nowX][nowY]) {
                        q.offer(new point(nowX, nowY));
                        visited[nowX][nowY] = true;
                    }
                }
            }
        }
        
        hm.put(num, cnt);
        return land;
    }
}

class point {
    int x, y;
    
    point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}