석유 시추

사용 알고리즘: dfs

사용 언어: 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 i=0; i<land.length; i++){
        //     System.out.println(Arrays.toString(land[i]));
        // }
        
        // System.out.println(map);
        
        //시추 시작
        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);
    }
}