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

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

🙋‍♂️ 들어가며

이번 문제는 시간복잡도를 생각하지 않으면 틀리는 문제였다

나는 우선 한번 BFS를 활용하여 3중 반복문

r = 0, r < 1
c = 0; c < col
k = 0; k < row

여기서 맨 첫 행에서 [0][0] ~ [0][col] 동안 확인하고 그때마다 각각 시추관의 크기를 0 ~ row까지 반복해서 점검하고자했다.

이 테스트케이스에서 맞길래 제출했는데 시간초과가 나서 오류였다.

일단 틀렸던 코드는 다음과 같다

❌틀린 코드 (시간초과)

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


class Solution {
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    static int max_oil = Integer.MIN_VALUE;


    public int solution(int[][] land) {

        // 열, 행
        int col = land[0].length;
        int row = land.length;

        for (int r = 0; r < 1; r++) {
            for (int c = 0; c < col; c++) {
                // 방문 맵
                boolean[][] visited = new boolean[row][col];

                // 임시횟수 (합산용)
                int temp_cnt = 0;

                // 시추관
                for (int k = 0; k < row; k++) {
                    // 최적화 (만약 방문했다면 skip)
                    if (visited[k][c]) continue;

                    // 빈땅이면 통과
                    if (land[k][c] == 0) continue;

                    // 방문 안했으면 방문처리후 temp_cnt에 추가, 그리고 q에 삽입
                    visited[k][c] = true;
                    temp_cnt++;
                    Queue<int[]> q = new LinkedList<>();
                    q.add(new int[] {k, c});

                    while (!q.isEmpty()) {
                        int[] cur_pos = q.poll();
                        int cr = cur_pos[0];
                        int cc = cur_pos[1];

                        for (int d = 0; d < 4; d++) {
                            int nr = cr + dr[d];
                            int nc = cc + dc[d];

                            // 범위 확인
                            if (nr < 0 || nr >= row || nc < 0 || nc >= col) continue;

                            // 다음 좌표가 빈땅이거나, 방문했으면 skip
                            if (land[nr][nc] == 0 || visited[nr][nc]) continue;

                            // 방문 안했으면 visitied 후 -> temp_cnt++ 그리고 q에 추가
                            visited[nr][nc] = true;
                            temp_cnt++;
                            q.add(new int[] {nr, nc});
                        }
                    }
                }
                // 비교
                max_oil = Math.max(max_oil, temp_cnt);

            }
        }


        return max_oil;
    }
}

틀린 이유를 알아보니 반례로 최악의 실행시간이 다음과 같더라

500 * 250000 * 500

즉 시간초과겠다.

🤔 다른 방법을 생각해보자

그렇다면 다른 방법을 생각해보니 완전탐색이 있더라

사진 1

사진 2

사진에 보는것처럼 노란색 점 을 현재 좌표로 가정하자.

초록색은 cnt++ 처리

빨간색 체크는 현재좌표가 석유와 이어져있는 column 이다.

각 사진마다 land[0][3], 그리고 land[4][6] 일때 HashSet에 석유가 있는 열들을 추가하여

oil_by_col = new int[열의 크기] 를 활용할 수 있지않을까?

이런 식으로 말이다

for (int col_idx : set) {
	oil_by_col[col_idx] += cnt;
}

위 사진 기준으로 land[0][3] 일때는 set에 3,4,5,6 추가
land[4][6] 일땐 set에 6,7 이 추가되겠다.

그러면 중복이 되지 않고도 좌표를 1개씩 완전탐색 하여 위의 배열에 추가할 수 있겠다.

이때의 최악의 실행시간은 다음과 같겠다

(500 * 500 * 4) + O(500)

-> 아 1억 이내 연산이라 시간초과 안나네 (good)

✅ 정답

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

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


class Solution {
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    static int max_oil = Integer.MIN_VALUE;
    static boolean[][] visited;
    static int row, col;
    
    public int solution(int[][] land) {
        row = land.length;
        col = land[0].length;
        visited = new boolean[row][col];
        
        // 완전탐색시 각 열마다 방문안한 좌표를 합산해주기 위한 배열
        int[] oil_by_col = new int[col];
        
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                // 만약 방문 안했고 + 석유라면
                if (!visited[r][c] && land[r][c] == 1) {
                    BFS(r, c, oil_by_col, land);
                }
            }
        }
        
        // 최대 비교
        for (int i : oil_by_col) {
            max_oil = Math.max(i, max_oil);
        }
        
        return max_oil;
    }
    
    
    
    
    
    static void BFS(int r, int c, int[] oil_by_col, int[][] land) {
        Queue<int[]> q = new LinkedList<>();
        
        // 석유덩어리가 겹치는 열을 oil_by_col에 반복문으로 저장해주기위해 Set 사용
        Set<Integer> set = new HashSet<>();
        
        int cnt = 0;
        
        // 지금 현재 좌표는 방문 안한 석유니까 -> cnt++;
        // 그리고 현재좌표의 열도 석유랑 맞닥드렸으니 set에 추가하자
        cnt++;
        set.add(c);
        
        visited[r][c] = true;
        q.add(new int[] {r, c});
        
        
        // 확인
        while (!q.isEmpty()) {
            int[] cur_pos = q.poll();
            int cr = cur_pos[0];
            int cc = cur_pos[1];
            for (int d = 0; d < 4; d++) {
                int nr = cr + dr[d];
                int nc = cc + dc[d];
                
                // 범위 밖이면 skip
                if (nr < 0 || nr >= row || nc < 0 || nc >= col) continue;
                
                // 다음좌표를 방문했거나, 빈땅이면 skip
                if (visited[nr][nc] || land[nr][nc] == 0) continue;
                
                // 미방문했다면 횟수 추가하고 방문처리
                visited[nr][nc] = true;
                cnt++;
                
                // 만약 col = 8일때, land[nr][nc] == 1
                // 그리고 그때의 nc가  0, 1, 4 -> set에 추가
                set.add(nc);
                q.add(new int[]{nr, nc});
            } 
        }
        
        // oil_by_col 에 set에 들은 열번호의 갯수만큼 반복하여 cnt 추가
        for (int col_idx : set) {
            oil_by_col[col_idx] += cnt;
        }
        
        
    }
    
    
    
}