[프로그래머스] lv2. 석유시추 [#BFS]

 

 

농심엔지니어링 최종 면접 다녀온 다음 날...

대전 자취방에서 인천 본가로 왔더니 넘나 쳐진다...

 

그래도 동생 컴으로 수업듣고 바로 알고리즘 한 문제 풀어본다!!

 

알고리즘 스터디에서 출제된 석유시추!!!

 

---

1. 출처

---

 

프로그래머스

 

풀어본 소감은 문제 자체는 쉬운데, 효율성 따지면서 풀기에는 생각하는 문제다...

 

 

 

---

2. 설계

---

 

 

오답 설계

혹시 틀려서 이 블로그까지 오신 분... 이렇게 풀지 않으셨나요?

 

1) 오일 영역 구분 -> BFS로 영역마다 갯수세기

2) 열마다 돌면서 다른 영역과 마주할 때마다 오일 갯수 갱신

 

설계 상으로 완벽해보이는 이 방법은 정확성 + 효율성 = 60점을 맞습니다.

 

 

그놈의 런타임 에러...

 

 

생각을 해보다가 2번 과정을 1번에 통합할 수 있겠다 생각했습니다.

 

 

정답 설계

 

1) 오일 영역 구분 -> BFS로 영역 갯수 세기 -> BFS마지막에 내가 지나온 COL 영역에 갯수 더해주기 -> MAX 비교 및 갱신

 

네... 1~2 과정을 통합해 한 번에 해주면 통과합니다.

 

 

 

---

3. 전체코드

---

 

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    
    static boolean[][] visited;
    static int[] colOilCount;
    
    static int[][] drc = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    
    static int maxOil = 0;
    
    public int solution(int[][] land) {
        
        int rowCount = land.length;
        int colCount = land[0].length;
        
        visited = new boolean[rowCount][colCount];
        colOilCount = new int[colCount];
        
        
        //1. 땅의 갯수와 해당 땅의 석유 수 구하기
        int count = 1;
        for(int i=0;i<rowCount;i++){
            for(int j=0;j<colCount;j++){
                if(land[i][j]==1 && !visited[i][j]){
                    BFS(land, i, j, count);
                    count++;
                }
            }
        }

        
        //2. 결과 도출
        return maxOil;
    }
    
    public static void BFS(int[][] land, int startR, int startC, int no){
        
        Queue<Node> q = new LinkedList<>();
        int size = 0;
        boolean[] colVisit = new boolean[land[0].length];
        
        //첫 노드 넣기
        q.offer(new Node(startR, startC));
        visited[startR][startC] = true;
        
        while(!q.isEmpty()){
            
            Node curNode = q.poll();
            size++;
            land[curNode.r][curNode.c] = no;
            colVisit[curNode.c] = true;
            
            for(int d=0; d<4; d++){
                int nextR = curNode.r+drc[d][0];
                int nextC = curNode.c+drc[d][1];
                
                if(nextR<0 || nextR>=land.length || nextC<0 || nextC>=land[0].length)
                    continue;
                if(land[nextR][nextC]==0 || visited[nextR][nextC]) continue;
                
                q.offer(new Node(nextR, nextC));
                visited[nextR][nextC] = true;
                
            }
            
        }
        
        //내가 지났던 COL 영역에 size 더해주기 -> max 비교 및 갱신
        for(int i=0;i<land[0].length;i++){
            if(colVisit[i]){
                colOilCount[i] += size;
                maxOil = Math.max(maxOil, colOilCount[i]);
            }
        }
        
    }
    
    public static class Node{
        int r;
        int c;
        public Node(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
}