[Java] 프로그래머스 - PCCP 기출문제 2번/석유 시추

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

프로그래머스

최초 코드

import java.util.*;

class Solution {
    private final int[] dy = {1,0,-1,0};
    private final int[] dx = {0,1,0,-1};
    
    private boolean[][] visited;
    //각 열의 석유 매장량 배열
    private int[] reserves;
    
    private int maxY;
    private int maxX;

    private int answer = 0;
    
    public int solution(int[][] land) {
        maxY= land.length;
        maxX= land[0].length;
        
        visited = new boolean[maxY][maxX];
        reserves = new int[maxX];

        for(int i=0; i<maxY; i++){
            for(int j=0; j<maxX; j++){
                if(!visited[i][j]&&land[i][j]==1){
                    visited[i][j]=true;
                    bfs(i, j, land);
                }
            }
        }
        Arrays.sort(reserves);
        
        return reserves[maxX-1];
    }
    
    //bfs알고리즘을 통해 상하좌우로 이동하며 덩어리에 속하는 모든 좌표를 찾고 각 열의 석유 매장량을 더해줌
    private void bfs(int i, int j, int[][] land){
        int oilCnt=1;
        List<int[]> oilCoordi = new ArrayList<>();
        oilCoordi.add(new int[]{i, j});
        
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{i, j});
        
        while(!q.isEmpty()){
            int[] coordi = q.poll();
            int y = coordi[0];
            int x = coordi[1];
                        
            for(int k=0; k<4; k++){
                int _y = y + dy[k];
                int _x = x + dx[k];
                
                if(isValidCoordi(_y, _x) && land[_y][_x]==1  && !visited[_y][_x]){
                    visited[_y][_x]=true;
                    q.offer(new int[]{_y, _x});
                    oilCoordi.add(new int[]{_y, _x});
                    oilCnt++;
                }
            }
        }
        
        boolean[] visitedX = new boolean[maxX];
        final int fixedOilCnt = oilCnt;
        
        oilCoordi.forEach(e->{
            if(!visitedX[e[1]]){
                visitedX[e[1]]=true;
                reserves[e[1]]+=fixedOilCnt;
            }
        });
    }
    
    private boolean isValidCoordi(int y, int x){
        return (0<=y&&y<maxY)&&(0<=x&&x<maxX);
    }
}

테스트케이스는 통과했으나 정확성 테스트와 효율성 테스트에서 실패했고 질문하기를 통해 반례를 찾을 수 있었다.

ㄷ, ㅁ, ㅂ 꼴과 같이 세변 이상으로 이어져 있는 덩어리의 경우 수직으로 탐색하다 중복으로 더하는 경우가 있기 때문에  해당 케이스에서 오답이 나온다는 것이다.

 

위 문제를 해결하기 위해 로직을 다시 생각했고 아래와 같은 답안을 제출할 수 있었다.

개선 코드

import java.util.*;

class Solution {
    private final int[] dy = {1,0,-1,0};
    private final int[] dx = {0,1,0,-1};
    private final Map<String, Integer> oilMass = new HashMap<>();
    private final List<Integer> reserves = new ArrayList<>();
    
    private boolean[][] visited;
    private int maxY;
    private int maxX;
    private int massNumber=0;

    private int answer = 0;
    
    public int solution(int[][] land) {
        maxY= land.length;
        maxX= land[0].length;
        
        visited = new boolean[maxY][maxX];

        for(int i=0; i<maxY; i++){
            for(int j=0; j<maxX; j++){
                if(!visited[i][j]&&land[i][j]==1){
                    visited[i][j]=true;
                    bfs(i, j, land);
                }
            }
        }
        
        //land의 각 열을 탐색하며 해당 열에서의 매장량 계산 -> 최대 매장량 갱신
        for(int i=0; i<maxX; i++){
            int oilSum=0;
            boolean[] isVisitedMass = new boolean[reserves.size()];                
            for(int j=0; j<maxY; j++){
                if(land[j][i]==1){
                    int _massNumber = oilMass.get(new StringBuilder().append("[").append(j).append(", ").append(i).append("]").toString());
                    if(isVisitedMass[_massNumber]){
                        continue;
                    }
                    isVisitedMass[_massNumber] = true;
                    oilSum += reserves.get(_massNumber);
                }
            }
            answer = Math.max(answer, oilSum);
        }
    
        return answer;
    }
    
    //주어진 좌표탐색 하여 각 좌표에 매장된 석유량 map에 추가
    private void bfs(int i, int j, int[][] land){
        int oilCnt=1;
        List<int[]> oilCoordi = new ArrayList<>();
        oilCoordi.add(new int[]{i, j});
        
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{i, j});
        
        while(!q.isEmpty()){
            int[] coordi = q.poll();
            int y = coordi[0];
            int x = coordi[1];
                        
            for(int k=0; k<4; k++){
                int _y = y + dy[k];
                int _x = x + dx[k];
                
                if(isValidCoordi(_y, _x) && land[_y][_x]==1  && !visited[_y][_x]){
                    visited[_y][_x]=true;
                    q.offer(new int[]{_y, _x});
                    oilCoordi.add(new int[]{_y, _x});
                    oilCnt++;
                }
            }
        }
        
        oilCoordi.forEach(e->oilMass.put(Arrays.toString(e), massNumber));
        massNumber++;
        reserves.add(oilCnt);
    }
    
    private boolean isValidCoordi(int y, int x){
        return (0<=y&&y<maxY)&&(0<=x&&x<maxX);
    }
}

각 열 탐색 시 이미 방문한 덩어리는 재방문하지 않도록 하면 되겠다는 생각을 했다.

 

bfs메서드를 호출할 때마다 같은 덩어리를 탐색하게 되므로 덩어리의 모든 좌표에 massNumber값을 부여해 map에 put했으며, 덩어리 number를 인덱스로 하는 list를 만들어 매장량을 value로 갖도록 했다.

 

그리고 land 2차원 배열을 수직 탐색 시 현재 좌표를 map의 키로 사용, massNumber를 get했고 이를 통해 재방문여부와 매장량을 계산할 수 있었다.

 

코드 개선을 위해 추가한 객체

//key: 석유가 매장돼있는 좌표 
//value: 좌표의 덩어리 번호
Map<String, Integer> oilMass = new HashMap<>();

//덩어리 번호를 인덱스로 하고 각 덩어리별 석유 매장량을 저장
List<Integer> reserves = new ArrayList<>();

//각 열을 시추할 때 이미 탐색한 덩어리인지 체크하기 위한 배열 생성
boolean[] isVisitedMass = new boolean[reverses.size()];

 

그  결과 정확성은 모두 맞을 수 있었고 효율성 테스트도 일부 통과할 수 있었다.

 

그러나, 최적화가 더 필요했다. 수십분동안 머리를 더 굴려 bfs시 알게된 정보를 이용해 기존의 수직 탐색(완탐) 로직을 사용하지 않는 아이디어를 생각해볼 수 있었다.

bfs로직에서 이미 한 덩어리에 대한 좌표값을 모두 구하고 있었고, 덩어리의 매장량 역시 카운트 되고 있었기 때문에 다음과 같은 로직으로 구현할 수 있었다.

 

1. 각 열의 매장량을 담는 배열을 생성 - int[] reserves = new int[maxX];

2. 좌표list를 순회하며 특정 열이 최초로 탐색되었을 때 reserves[열]+= oilCnt; 

3. 해당 열을 방문 처리

 

이렇게 각 열의 매장량을 전보다 훨씬 효율적으로 구할 수 있었고, 한번의 완전탐색이후 배열을 정렬한 뒤 마지막 인덱스를 return 해주어 문제를 해결할 수 있었다.

최종 코드

import java.util.*;

class Solution {
    private final int[] dy = {1,0,-1,0};
    private final int[] dx = {0,1,0,-1};
    
    private boolean[][] visited;
    private int[] reserves;
    
    private int maxY;
    private int maxX;

    private int answer = 0;
    
    public int solution(int[][] land) {
        maxY= land.length;
        maxX= land[0].length;
        
        visited = new boolean[maxY][maxX];
        reserves = new int[maxX];

        for(int i=0; i<maxY; i++){
            for(int j=0; j<maxX; j++){
                if(!visited[i][j]&&land[i][j]==1){
                    visited[i][j]=true;
                    bfs(i, j, land);
                }
            }
        }
        Arrays.sort(reserves);
        
        return reserves[maxX-1];
    }
    
    //주어진 좌표탐색 하여 각 좌표에 매장된 석유량 map에 추가
    private void bfs(int i, int j, int[][] land){
        int oilCnt=1;
        List<int[]> oilCoordi = new ArrayList<>();
        oilCoordi.add(new int[]{i, j});
        
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{i, j});
        
        while(!q.isEmpty()){
            int[] coordi = q.poll();
            int y = coordi[0];
            int x = coordi[1];
                        
            for(int k=0; k<4; k++){
                int _y = y + dy[k];
                int _x = x + dx[k];
                
                if(isValidCoordi(_y, _x) && land[_y][_x]==1  && !visited[_y][_x]){
                    visited[_y][_x]=true;
                    q.offer(new int[]{_y, _x});
                    oilCoordi.add(new int[]{_y, _x});
                    oilCnt++;
                }
            }
        }
        
        boolean[] visitedX = new boolean[maxX];
        final int fixedOilCnt = oilCnt;
        
        oilCoordi.forEach(e->{
            if(!visitedX[e[1]]){
                visitedX[e[1]]=true;
                reserves[e[1]]+=fixedOilCnt;
            }
        });
    }
    
    private boolean isValidCoordi(int y, int x){
        return (0<=y&&y<maxY)&&(0<=x&&x<maxX);
    }
}

 

그 결과 시간을 절반가량 줄이며 효율성 테스트까지 통과할 수 있었다.