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

사용 알고리즘: bfs, 메모이제이션..?

사용 언어: java

 

import java.util.*;
import java.awt.*;

class Solution {
    public int solution(int[][] land) {
        int[] res = new int[land[0].length];
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        int landName = 2;
        for(int i=0; i<land.length; i++){
            for(int j=0; j<land[0].length; j++){
                if(land[i][j] == 1) {
                    land[i][j] = landName;
                    bfs(i,j, landName, 1, map, land.length, land[0].length, land);
                    landName++;
                }
            }
        }
        
        //시추 시작
        for(int j=0; j<land[0].length; j++){
            int sum = 0;
            boolean[] meet = new boolean[map.size()+2];
            for(int i=0; i<land.length; i++){
                if(land[i][j] != 0){
                    meet[land[i][j]] = true;
                }
            }
            
            for(int w=2; w<map.size()+2; w++){
                if(meet[w]) sum += map.get(w);
            }
            res[j] = sum;
        }
        
        
        return Arrays.stream(res).max().getAsInt();
    }
    
    private static void bfs(int x, int y, int ln, int sum, HashMap<Integer, Integer> map, int r, int c, int[][] land) {
        
        int dx[] = {1,-1,0,0};
        int dy[] = {0,0,1,-1};
        Queue<Point> q = new ArrayDeque<>();
        q.offer(new Point(x,y));
        
        while(!q.isEmpty()){
            Point p = q.poll();
            for(int d=0; d<4; d++){
                int nx = p.x+dx[d];
                int ny = p.y+dy[d];
                
                if(nx>=0 && nx<r && ny>=0 && ny<c && land[nx][ny]==1){
                    land[nx][ny] = ln;
                    sum++;
                    q.offer(new Point(nx,ny));
                }
            }
        }
        map.put(ln, sum);
    }
}

 

 

효율성 테스트:

시추할 때마다 넓이를 구하면 효율성이 많이 떨어짐

1. land를 미리 돌면서 각 구역의 넓이를 map 형태로 미리 저장 + 각 구역마다 고유 번호 부여 map = (고유번호, 넓이)

2. 시추 시에는 고유 번호 중 만나는 곳만 boolean[]으로 체크해서 map.get(고유 번호) =넓이의 합계를 구하기

 

 

이슈:

IDE 없이 자바를 사용하기 어렵..

IDE에 비해 작은 창에서 코딩을 하다보니 문제가 생겼을 때 한눈에 안 보임..

 

맵 + 파라미터로 넘길 때

static 변수 사용하지 않는 연습하기