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

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/250136#

프로그래머스

 

풀이과정

각 열 마다 하나씩 아래로 내려가며 탐색을 수행합니다. 이때 이미 계산 된 영역은 다시 계산하지 않기 위해 메모리제이션을 해줘야 합니다. 메모리제이션을 위해 영역벌 번호를 할당하고 HashMap을 활용해 그 크기를 저장했습니다.

 

메모리제이션

1. 석유인 영역(1)을 만나게 되면, 해당 영역의 크기를 bfs로 확인합니다. 이때, 영역별 번호 (저는 -1,-2,-3 ... 음수로 표현했습니다)와 해당 영역별 번호에 해당하는 크기를 HashMap 자료구조에 저장합니다. 

int bfs(int r,int c,int[][] land,int area_num){
        Deque<int[]> q = new ArrayDeque<>();
        // boolean[][] visited = new boolean[H][W]; // 이 코드 때문에 효율성 테스트 2번과 3번에서 시간초과가 났다.
        
        q.offer(new int[]{r,c});
        land[r][c] = area_num;
        // visited[r][c] = true;
        int result = 1;
        
        while(!q.isEmpty()){
            int[] cur = q.pollFirst();
            int cr = cur[0];
            int cc = cur[1];
            
            for(int d=0;d<4;d++){
                int nr = cr + dr[d];
                int nc = cc + dc[d];
                
                if(nr<0 || nr>=H) continue;
                if(nc<0 || nc>=W) continue;
                // if(visited[nr][nc]) continue;
                if(land[nr][nc]==1){
                    result+=1;
                    land[nr][nc] = area_num;
                    // visited[nr][nc]=true;
                    q.offer(new int[]{nr,nc});
                }
            }
        }
        
        map.put(area_num,result);
        
        return result;
    }

매개변수로 넘겨받은 area_num을 통해 방문처리를 한 번에 진행할 수 있습니다. 이 문제에서 boolean을 활용하게 된다면 효율성체크에서 시간초과가 발생했습니다.

 

2. 만약 아래로 내려가다 음수인 영역(이미 계산된 영역)을 만나게 되면 그 영역의 크기 HashMap에서 가져와 더해줍니다.

이때 이미 저장한 영역은 다시 저장하지 않아야 하기때문에 HashSet을 사용했습니다. 

1 1 1 1 
1 0 0 0
1 0 1 0
1 0 0 0
1 1 1 1

위 예제와 같이 ㄷ자로 된 경우 set으로 확인한 영역에 대해 처리하지 않으면 중복으로 영역의 값이 추가되는 문제가 있습니다.

 

또한 1번 과정에서 bfs수행 후, set영역에 바로 추가를 해줘야 합니다. 그렇지 않으면 다음 턴에 한 번 더 값이 계산되는 문제가 발생합니다. 아래 코드를 보면 land[r][c]==1 인 경우, bfs를 수행하고 set에 바로 add해줬습니다.

if(land[r][c]==1){
                    cnt += bfs(r,c,land,area_num);
                    set.add(land[r][c]);
                    area_num--;
                }else if(land[r][c]<0 && !set.contains(land[r][c])){ // 이미 확인한 영역이면 그 값 활용
                    cnt += map.get(land[r][c]);
                    set.add(land[r][c]);
                }

 

 

 

알게된 점

• 무작정 구현하지 말고, 효율성을 줄일 수 있는 방법 (메모리제이션)을 잘 생각해볼 수 있었던 문제였습니다.
• 특히 처음에는 bfs수행 시 boolean[][] 배열로 방문처리를 해줬는데, 이 문제에서 방문처리를 이미 영역 번호(area_num)으로 해주기 때문에 boolean[][] 배열이 필요없었습니다. 중복된 기능이 있는 코드를 줄여서 시간을 줄일 수 있음을 배웠습니다.

전체코드

import java.util.*;

class Solution {
    
    int[] dr = {-1,0,1,0};
    int[] dc = {0,1,0,-1};
    int W,H;
    Map<Integer,Integer> map;
    
    int bfs(int r,int c,int[][] land,int area_num){
        Deque<int[]> q = new ArrayDeque<>();
        // boolean[][] visited = new boolean[H][W]; // 이 코드 때문에 효율성 테스트 2번과 3번에서 시간초과가 났다.
        
        q.offer(new int[]{r,c});
        land[r][c] = area_num;
        // visited[r][c] = true;
        int result = 1;
        
        while(!q.isEmpty()){
            int[] cur = q.pollFirst();
            int cr = cur[0];
            int cc = cur[1];
            
            for(int d=0;d<4;d++){
                int nr = cr + dr[d];
                int nc = cc + dc[d];
                
                if(nr<0 || nr>=H) continue;
                if(nc<0 || nc>=W) continue;
                // if(visited[nr][nc]) continue;
                if(land[nr][nc]==1){
                    result+=1;
                    land[nr][nc] = area_num;
                    // visited[nr][nc]=true;
                    q.offer(new int[]{nr,nc});
                }
            }
        }
        
        map.put(area_num,result);
        
        return result;
    }
   
    
    public int solution(int[][] land) {
        int answer = 0;
        W = land[0].length;
        H = land.length;
        map = new HashMap<>();
        Set<Integer> set;
        int area_num = -1;
        
        for(int c=0;c<W;c++){
            int cnt = 0;
            set = new HashSet<>();
            for(int r=0;r<H;r++){
                if(land[r][c]==1){
                    cnt += bfs(r,c,land,area_num);
                    set.add(land[r][c]);
                    area_num--;
                }else if(land[r][c]<0 && !set.contains(land[r][c])){ // 이미 확인한 영역이면 그 값 활용
                    cnt += map.get(land[r][c]);
                    set.add(land[r][c]);
                }
            }
            answer = Math.max(answer,cnt);
        }
        
        return answer;
    }
}