PGMRS_석유 시추(PCCP 기출, JAVA)

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

프로그래머스

 

문제의 첫 문단을 읽으면 BFS라는 것을 알게 된다.

import java.util.*;

class Solution {
    // 발견하기
    // 1. 열을 하나씩 탐색하면서 석유가 가장 많은 곳을 뚫는 것은 의미가 없다.
    // 2. 이 문제는 BFS이며, 선택한 열의 모든 요소를 큐에 집어넣고 시작한다.
    // 3. 일단 모든 열에 대해 BFS를 돌리고, 가장 많은 값을 가진 열을 찾는 걸로 시작하면 어떨까?
    
    static boolean[][] visited;
    static int[][] land;
    static Queue<Idx> Q;
    static int result; // 답
    
    static class Idx {
        int r, c;
        Idx (int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    
    public int solution(int[][] land) { // 석유가 있으면 1, 없으면 0
        this.land = land;
        
        for(int i = 0; i<land[0].length; i++){
            int thisResult = lineSearch(i);
            if(result < thisResult) result = thisResult;
        }
        
        return result;
    }
    
    public int lineSearch(int colNum){ // 열마다의 BFS 수행 결과(석유의 수)를 리턴한다.
        visited = new boolean[land.length][land[0].length];
        Q = new LinkedList<>();
        
        for(int i = 0; i<land.length; i++){
            if(land[i][colNum] > 0) {
                visited[i][colNum] = true; // **큐에 넣기 전에** 방문체크를 해 준다.
                Q.add(new Idx(i, colNum));
            }
        }
        
        int sum = 0;
        while(!Q.isEmpty()){
            Idx i = Q.poll();
            sum += BFS(i);
            // 사실 while문이 수행된 후 visited[][] 배열의 요소 총합을 구해도 된다.
            // 그런데 이 과정을 또 수행하려면 O(NM)가 들기 때문에
            // 탐색 중인 요소에서 바로바로 1씩 리턴하고, 더하는 형식을 택했다. 절대 순회 코드 치기 귀찮아서가 아님
        }
        
        return sum;
    }
    
    public int BFS(Idx idx) {
        
        // 상하좌우 델타배열
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        
        for(int i = 0; i<4; i++){
            int nr = idx.r + dr[i];
            int nc = idx.c + dc[i];
            if(nr < 0 || nr >= visited.length || nc < 0 || nc >= visited[0].length) 
                continue;
            if(land[nr][nc] == 0) continue;
            if(visited[nr][nc] == true) continue;
            
            visited[nr][nc] = true;
            Q.add(new Idx(nr, nc));
        }
        
        return 1;
    }
}

처음에는 이렇게 단순하게 접근해서 풀이를 했다. 그랬더니

이제는 걍 너무 익숙함

 

역시 효율성에서 빵점이 나온다 .... 이거 왜 이러냐면

매 열마다 새로 BFS를 시작하기 때문이다 ㅋㅋ

탐색한 곳을 또 탐색하고 ...

다음 열에서는 또 까먹고 또 탐색하고 ... 방금 전에 파 본 구덩이인데도 매번 초행길이 되는 셈

그래서 좀 고민을 해 보았다. 어떻게 하면 좋을까?

어떻게 하면 이미 들어가 본 구덩이라는 것을 알 수 있을 것인가

 

---

고민을 좀 해 본 결과, 방문 배열로 사용하고 있던 bool[][] visited의 구조를 int[][] 타입의 newLand로 바꿔서

방문 체크 겸 구덩이의 ID를 쓰기로 했다. 

그리고 이번에는 BFS를 열마다 새로 수행하지 않는다. 전체적으로 한 번만 수행할 것임

코드 구조가 전반적으로 바뀌었음. 핵심은 다음과 같다.

1) BFS를 전체 배열에서 순회하며 같은 구덩이라면 newLand에서도 같은 값(=구덩이 ID)을 가지도록 함

2) 구덩이 ID와 사이즈를 저장하는 oilPots라는 이름의 HashMap<Integer, Integer>을 만들었다

3) 열마다 탐색하며 발견한 구덩이 ID를 저장하는 found라는 이름의 HashSet<Integer>를 만들었다

4) 열마다 각 요소를 탐색하면서, 구덩이를 발견함 > found에 있는 구덩이가 아님 > oilPots.get(구덩이ID)를 result에 더함

요런 식으로 진행될 것이다.

 

아래의 코드로 작성했다. 

본문에서 구덩이라고 부른 것이 여기에서는 덩어리이므로 주의 ㅋㅋ

import java.util.*;

class Solution {
    // 발전시키기
    // 1. 발견할 수 있는 모든 석유 덩어리에 대한 정보를 저장해 보자. 
    // 2. 열마다 지금까지 방문한 덩어리 정보를 저장해 보자.
    // 3. 해당 열에서 이미 방문한 석유 덩어리라면, continue
    
    static class Idx {
        int r, c;
        Idx (int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    
    static HashMap<Integer, Integer> oilPots;
    static HashSet<Integer> found;
    static Queue<Idx> Q;
    static int[][] land, newLand; // 초기 BFS 시 land를, 열 단위 탐색 시 newLand를 사용하게 된다.
    static int result;
    
    // 상하좌우 델타배열
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    
    public int solution(int[][] land) {
        init(land);
        for(int i = 0; i<land[0].length; i++){
            int thisResult = lineSearch(i);
            if(thisResult > result) result = thisResult;
        }
        return result;
    }
    
    public int lineSearch(int colNum){ // 열마다 발견할 수 있는 덩어리의 크기를 반환한다.
        found = new HashSet<>(); // 탐색 중인 열에서 찾은 덩어리 ID를 저장하는 Set
        int result = 0;
        for(int i = 0; i<newLand.length; i++){
            if(newLand[i][colNum] > 0){
                if(!found.contains(newLand[i][colNum])) {
                    found.add(newLand[i][colNum]);
                    result += oilPots.get(newLand[i][colNum]);
                }
            }
        }
        
        return result;
    }
    
    public void init(int[][] land){ // 변수 초기화, initBFS를 호출한다.
        Q = new LinkedList<>();
        this.land = land;
        newLand = new int[land.length][land[0].length];
        oilPots = new HashMap<>();
        
        for(int i = 0; i<land.length; i++){
            for(int j = 0; j<land[0].length; j++){
                if(land[i][j] == 1 && newLand[i][j] == 0){
                    newLand[i][j] = oilPots.size()+1; // 방문체크 겸 덩어리 ID 부여
                    Q.add(new Idx(i, j));
                    oilPots.put(newLand[i][j], initBFS());
                }
            }
        }
    }
    
    public int initBFS(){ // 덩어리의 크기를 반환함
        int result = 1; // 초기 위치가 포함된 덩어리 크기
        while(!Q.isEmpty()){
            Idx curr = Q.poll();
            for(int i = 0; i<4; i++){
                int nr = curr.r + dr[i];
                int nc = curr.c + dc[i];
                if(nr >= 0 && nr < newLand.length && 
                   nc >= 0 && nc < newLand[0].length){
                    if(land[nr][nc] == 1 && newLand[nr][nc] == 0){
                        newLand[nr][nc] = newLand[curr.r][curr.c];
                        result++;
                        Q.add(new Idx(nr, nc));
                    }
                }
            }
        }
        
        return result;
    }
    

}

 

효율성 테스트까지 통과하려면, 자료구조의 특성을 다양하게 알아 두는 것이 짱(..?) 도움이 될 것 같다. 

문제 요건에 맞게 구조화를 하는 과정이 진짜 재밌는데 ....

코드가 길어질수록 작은 데서 오류 생기면 너무 막막해진다 ...