[프로그래머스/LV2] 석유시추 - bfs (Java)

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

🙋‍♂️ 들어가며

• row <= 500
• col <= 500

상황에서 각좌표마다 그냥 bfs를 하면 25000 * 500 * 500으로 시간초과였다.

그래서 각 좌표마다 1번씩만 돌아서 최악의 연산횟수가 총 250000으로 만들어질 필요가 있었다.

그러려면 방문한 좌표는 더이상 방문하면 안됬었고 이를 위해 Set을 추가하였으며

석유에 인접한 열번호를 추가하고자 하였다.

입출력예 2번 기준으로 land[0][0] 일때 석유인 곳을 계속 방문하여 연결하면

set = {0, 1, 2, 3, 4, 5, 6}

즉 모든 열번호가 들어오게 된다

그 과정에서 석유를 찾을 때마다 석유 시작점 1에서 ++를 해주었고

bfs 종료 후에, column_arr에 set의 번호를 적용해 총 석유의 갯수를 더해주었다

이 과정은 O(row*col) 이며 코드는 다음과 같다

✅ 정답

import java.util.Set;
import java.util.HashSet;

import java.util.ArrayDeque;
import java.util.Queue;


class Solution {
    static int answer;
    static int row, col;
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    
    
    public int solution(int[][] land) {
        answer = 0;
        
        // O(row * col)
        // visited 배열로 이미 방문한 곳은 재방문 없이 25만 이내에 해결
        // column을 중복없이 저장하기 위해 Set
        
        // 1-1. 완전탐색
        row = land.length;
        col = land[0].length;
        boolean[][] visited = new boolean[row][col];
        int[] column_arr = new int[col];
        
        for (int r = 0; r < row; r++) {
           for (int c = 0; c < col; c++) {
               // 1-2. 1이고 방문 안했으면 bfs
               if (land[r][c] == 1 && !visited[r][c]) {
                   int sr = r;
                   int sc = c;
                   bfs(sr, sc, land, visited, column_arr);
               }
           }
        }
        
        // 3. 각 열마다 검사하여 최댓값 추출
        for (int i = 0; i < column_arr.length; i++) {
            answer = Math.max(column_arr[i], answer);
        }
        return answer;
    }
    
    
    
    
    // 2. 함수 (bfs)
    static void bfs(int cr, int cc, int[][] land, boolean[][] visited, int[] column_arr) {
        
        // 2-0. 석유영역 갯수 (현재영역도 석유라서 1부터 시작)
        int cnt = 1;
        
        // 2-1. Set 생성, q생성
        Set<Integer> col_no = new HashSet<>();
        Queue<int[]> q = new ArrayDeque<>();
        
        // 2-2. 초기값 true 처리후, q에 삽입, 컬럼번호 추가
        visited[cr][cc] = true;
        q.add(new int[] {cr, cc});
        col_no.add(cc);
        
        // 2-3. q가 비지않았을 때까지 검사
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cur_r = cur[0];
            int cur_c = cur[1];
            for (int d = 0; d < 4; d++) {
                int nr = cur_r + dr[d];
                int nc = cur_c + dc[d];
                
                // 2-3-a. 만약 범위 밖이면 -> continue;
                if (nr < 0 || nr >= row || nc < 0 || nc >= col) continue;
                
                // 2-3-b. 만약 이미 방문했거나, 흙이면 skip
                if (visited[nr][nc] || land[nr][nc] == 0) continue;
                
                // 2-3-c. 범위안, 미방문, 석유면?
                visited[nr][nc] = true;
                cnt++;
                q.add(new int[] {nr, nc});
                col_no.add(nc);
            }
        }
        
        // 2-4. 석유 걸치고 있는 영역 갯수에 반영
        for (int no : col_no) {
            column_arr[no] += cnt;
        }

        // 2-5. 종료
        return;
    }
    
    
}