프로그래머스 석유시추 (java)

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

---

관찰

1. 덩어리를 파악해야하니 dfs, bfs 둘 중 하나를 사용해서 영역을 파악해야한다.
2. 일단 가로길이 500번을 전부 땅을 파보면서 dfs를 돌릴려고 하니 비효율적이라는 생각
3. 이런 문제는 전처리를 통해 한번에 계산할 수 있도록 만들어줘야 한다.
4. 각 열마다의 정답을 구해줘서 dfs를 최대한 적게 돌릴 수 있도록 풀어보자

---

정답 코드

import java.util.*;
import java.io.*;

class Solution {
    static int n,m,k;
    static int[] res,check;
    static int[][] visited, map; 
    static int[] dr = {-1,0,1,0};
    static int[] dc = {0,1,0,-1};
    public int solution(int[][] land) {
        int answer = 0;
        n = land.length;
        m = land[0].length;
        
        res = new int[m];
        visited = new int[n][m];
        map = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                map[i][j] = land[i][j];
            }
        }
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(land[i][j] == 1&& visited[i][j] == 0){
                    check = new int[m];
                    k = 1;
                    dfs(i,j);
                    // check 된 부분들만 영역의 크기인 k를 더해준다
                    for(int ii=0;ii<m;ii++){
                        if(check[ii] == 1) res[ii] += k;
                    }
                }
            }
        }
        
        for(int i=0;i<m;i++){
            if(answer < res[i]) answer = res[i];
        }
        return answer;
    }
    
    public void dfs(int r,int c){
        visited[r][c] = 1;
        if(check[c] == 0) check[c] = 1;
        for(int i=0;i<4;i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(nr >= n || nr < 0 || nc >= m || nc < 0) continue;
            if(map[nr][nc] == 0) continue;
            if(visited[nr][nc] == 1) continue;
            k++;
            dfs(nr,nc); 
        }
    }
}

---

풀이

처음 생각했던 방식 - 각 열마다 하나씩 땅 파면서 dfs를 돌려보기

완전탐색 방식인데 그렇다면 중복해서 검사하는 부분이 많이 보인다

정답 코드 방식 - 맵에 있는 석유 영역 한번씩만 탐색

한번씩만 탐색하는 방식으로 그 영역이 영향을 주는 열을 배열에 담아 각 열의 정답을 빠르게 구하고 마지막에 가장 큰 값을 출력

---

한줄 정리

항상 완전탐색을 먼저 생각한 후에 중복된 부분은 없는 지, 전처리 할 수 있는 부분이 없는 지 생각하면서 풀어야 하는 것 같다.