[Programmers][Python] 프로그래머스: 석유 시추

1일 1PS 88일차!

📚 문제

---

[Level 2] - 석유 시추

💡 풀이 과정

---

• 석유 매장량을 파악하고 각 위치에서의 총 시추량을 구해야한다.
• 각 석유 매장량은 BFS 를 통해 파악할 수 있다. 처음 시작 시 index 로 구분지어 각 석유 매장량이 얼마인지 파악할 필요가 있다.

• 이후 각 위치에서의 석유 매장량을 검사한다.

• (TLE) land 의 석유를 각 index 로 변경하고 실제 가로 위치에 존재하는 석유를 파악해 해당 위치의 시추량을 구했다.
• (TLE) 가로 길이만큼의 Set 을 생성하고 BFS 를 진행하면서 각 가로 위치에 석유 매장 index 를 추가하고 이후 시추량을 구했다.
• (AC) 가로 길이만큼의 int[] 를 생성해놓고 BFS 를 진행하면서 가로 위치를 Set 으로 저장하고 마지막에 Set 에 저장된 위치에 해당 index 의 석유량을 더해주었다.

📌포인트

---

• index
  • 기존 0, 1 로 구성된 land 를 교체할 때는 헷갈리지 않게 2부터 시작하도록 하자.
• BFS
  • BFS 진행 시 처음 값에 주의해야한다. visited 및 set 에 추가..

💻 코드

---

import java.util.*;

class Solution {
    static Set<Integer>[] oils_index;
    static int[] answers;
    
    public int solution(int[][] land) {
        int idx = 0;
        int N = land.length;
        int M = land[0].length;
        
        oils_index = new HashSet[M];
        for(int i = 0; i < M; i++){
            oils_index[i] = new HashSet<>();
        }
        answers = new int[M];
        
        List<Integer> oils = dfs(land, N, M);      
        
        return Arrays.stream(answers).max().getAsInt();
    }
    
    public static LinkedList<Integer> dfs(int[][] land, int N, int M){
        boolean[][] visited = new boolean[N][M];
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        int idx = 2;
        LinkedList<Integer> oils = new LinkedList<>();
        
        
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(visited[i][j] == true || land[i][j] == 0){
                    continue;
                }
                
                Set<Integer> oils_idx = new HashSet<>();

                Queue<int[]> queue = new LinkedList<>();
                queue.add(new int[]{i, j});
                int cnt = 1;
                land[i][j] = idx;
                oils_idx.add(j);
                while(!queue.isEmpty()){
                    int[] pop = queue.poll();
                    for(int k = 0; k < 4; k++){
                        int nx = pop[0] + dx[k];
                        int ny = pop[1] + dy[k];
                        
                        if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny] || land[nx][ny] == 0){
                            continue;
                        }
                        
                        if(land[nx][ny] == 1){
                            cnt++;
                            queue.add(new int[]{nx, ny});
                            land[nx][ny] = idx;
                            visited[nx][ny] = true;
                            oils_idx.add(ny);
                        }
                    }
                }
                if(cnt >= 1){
                    oils.add(cnt);
                    idx++;
                    for (int index : oils_idx){
                        answers[index] += cnt;
                    }
                }
            }
        }
        return oils;
    }
}