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

21 Apr 2023 in Algorithm on Algorithm

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

import java.util.*;

class Solution {
    private int[] dx = {-1, 0, 1, 0};
    private int[] dy = {0, -1, 0, 1};
    private Map<Integer, Integer> resultMap = new HashMap<>();

    public int solution(int[][] land) {
        int answer = 0;
        int xLen = land.length;
        int yLen = land[0].length;

        bfs(land, xLen, yLen);

        for(int y = 0; y < yLen; y++) {
            Map<Integer, Boolean> visited = new HashMap<>();
            int cnt = 0;
            for (int x = 0; x < xLen; x++) {
                int groupId = land[x][y];
                if(!visited.containsKey(groupId) && groupId > 0) {
                    visited.put(groupId, true);
                    cnt += resultMap.get(groupId);
                }
            }
            answer = Math.max(answer, cnt);
        }

        return answer;
    }

    private void bfs(int[][] land, int xLen, int yLen){

        Queue<int[]> q = new LinkedList<>();
        boolean[][] visited = new boolean[xLen][yLen];
        int groupId = 2;

        for(int x = 0; x < xLen; x++){
            for(int y = 0; y < yLen; y++){
                if(!visited[x][y] && land[x][y] == 1){
                    q.add(new int[]{x, y});
                    visited[x][y] = true;
                    land[x][y] = groupId;
                    int cnt = 1;
                    while(!q.isEmpty()){
                        int[] cur = q.poll();
                        for(int i = 0 ; i < 4 ; i++){
                            int nx = cur[0] + dx[i];
                            int ny = cur[1] + dy[i];
                            if( nx >= 0 && ny >=0 && nx < xLen && ny < yLen && land[nx][ny] == 1 && !visited[nx][ny]){
                                visited[nx][ny] = true;
                                land[nx][ny] = groupId;
                                q.add(new int[]{nx, ny});
                                cnt++;
                            }
                        }
                    }
                    resultMap.put(groupId, cnt);
                    groupId++;
                }
            }
        }
    }
}