[JAVA/BFS] 석유 시추

https://school.programmers.co.kr/learn/courses/30/lessons/250136

프로그래머스

 

import java.util.*;

class Solution {
    
    // 각 열별로 얻을 수 있는 석유의 총양
    int[] total;
    // 탐색 여부
    private boolean[][] visited;
    // 정답
    private int max = 0;
     
    public int solution(int[][] land) {
        
        // 입력된 land의 크기에 따라 필요한 배열 크기 지정
        total = new int[land[0].length];
        visited = new boolean[land.length][land[0].length];
        
        // 0이 아닌 값을 탐색하며 서로 다른 석유 덩어리 탐색
        for(int i=0; i<land.length; i++) {
            for(int j=0; j<land[i].length; j++) {
                if(land[i][j] == 0 || visited[i][j] ) {
                    continue;
                }
                else {
                    bfs(i, j, land);
                }
            }
        }
        
        // 정답 반환
        return max;
    }
    
    public void bfs(int row, int col, int[][] land) {
        
        // BFS용 큐와 해당 석유 덩어리가 있는 열 식별
        Queue<Integer[]> q = new LinkedList<>();
        Set<Integer> colSet = new HashSet<>();
        
        // 초기값 세팅
        q.add(new Integer[]{row, col});
        visited[row][col] = true;
        
        // 해당 석유 덩어리의 크기
        int cnt = 0;
        
        while(!q.isEmpty()) {
            cnt++;
            
            Integer[] qPoll = q.poll();
            int rowTmp = qPoll[0];
            int colTmp = qPoll[1];
            
            colSet.add(colTmp);
            
            // 상하좌우를 살피며 동일한 석유덩어리 식별
            if(rowTmp != 0 && land[rowTmp-1][colTmp] == 1 && !visited[rowTmp-1][colTmp]) {
                q.add(new Integer[]{rowTmp-1, colTmp});
                visited[rowTmp-1][colTmp] = true;
            }
            if(rowTmp != land.length-1 && land[rowTmp+1][colTmp] == 1 && !visited[rowTmp+1][colTmp]) {
                q.add(new Integer[]{rowTmp+1, colTmp});
                visited[rowTmp+1][colTmp] = true;
            }
            if(colTmp != land[0].length-1 && land[rowTmp][colTmp+1] == 1 && !visited[rowTmp][colTmp+1]) {
                q.add(new Integer[]{rowTmp, colTmp+1});
                visited[rowTmp][colTmp+1] = true;
            }
            if(colTmp != 0 && land[rowTmp][colTmp-1] == 1 && !visited[rowTmp][colTmp-1]) {
                q.add(new Integer[]{rowTmp, colTmp-1});
                visited[rowTmp][colTmp-1] = true;
            }
        }
        
        // 해당 석유 덩어리가 존재하는 열에 석유 덩어리의 크기 저장 후 max 식별
        for(int colTmp : colSet) {
            total[colTmp] += cnt;
            max = Math.max(total[colTmp], max);
        }
        
    }
    
    
}