[프로그래머스]PCCP 기출 2번 Java 풀이(반례 포함)

사이트 링크

https://school.programmers.co.kr/learn/courses/19344/lessons/242259

프로그래머스

 

개념 및 풀이

1. 석유 덩어리의 크기를 각 칸에 저장(visit[][])
2. 같은 덩어리인지의 표기를 위해 layer[][]를 통해 덩어리 숫자 표기
3. 이중 for문 돌면서 덩어리 크기와, 같은 덩어리인지 다른덩어리인지 확인 후 값 더하기

- 반례

land(int[][])	Return
[[0,0,1,1,0],[0,0,0,0,0],[1,1,1,0,0],[0,0,1,0,0],[1,1,1,0,0]]	9

 

 

코드

import java.util.*;
class Solution {
    static class Pos{
        int x,y;
        Pos(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static int[][] deltas = {{0,1},{0,-1},{1,0},{-1,0}};
    static int[][] visit,layer;
    
    public int solution(int[][] land) {
        int answer = 0;
        visit = new int[land.length][land[0].length];
        layer = new int[land.length][land[0].length];
        int depth = 1;
        for(int i=0;i<land.length;i++) {
            for(int j=0;j<land[0].length;j++) {
                if(land[i][j]==1 && visit[i][j]==0) {
                    bfs(i,j,land,depth++);
                }
            }
        }
        
        
        for(int j=0;j<land[0].length;j++) {
            int sum = 0;
            ArrayList<Integer> alist = new ArrayList<>();
            Loop: for(int i=0;i<land.length;i++) {
                if(land[i][j]==1) {
                    for(int a:alist){
                        if(layer[i][j] == a) continue Loop;
                    }
                    sum += visit[i][j];
                    alist.add(layer[i][j]);
                }
            }
            answer = Math.max(sum,answer);
        }
        
        // print(visit);
        // System.out.println();
        // print(layer);
        return answer;
    }
    static int bfs(int x, int y, int[][] land,int depth) {
        int oil = 1;
        
        Queue<Pos> q = new LinkedList<>();
        q.offer(new Pos(x,y));
        
        Queue<Pos> oilPos = new LinkedList<>();
        oilPos.offer(new Pos(x,y));
        
        visit[x][y]++;
        
        layer[x][y] = depth;
        
        while(!q.isEmpty()) {
            Pos now = q.poll();
            
            for(int d=0;d<4;d++) {
                int dx = now.x + deltas[d][0];
                int dy = now.y + deltas[d][1];
                
                if(dx>=0 && dy>=0 && dx<land.length && dy<land[0].length && land[dx][dy]==1 && visit[dx][dy]==0){
                    visit[dx][dy]++;
                    oil++;
                    
                    oilPos.offer(new Pos(dx,dy));
                    q.offer(new Pos(dx,dy));
                    
                    layer[dx][dy] = depth;
                }
            }
        }
        
        while(!oilPos.isEmpty()) {
            Pos now = oilPos.poll();
            visit[now.x][now.y] = oil;
        }
        
        return oil;
    }
    
    static void print(int[][] visit){
        for(int i=0;i<visit.length;i++) {
            for(int j=0;j<visit[0].length;j++) {
                System.out.print(visit[i][j]+" ");
            }
            System.out.println();
        }
    }
}