프로그래머스 (PCCP) | LV.2 석유 시추 - BFS/DFS + 구현 문풀 (Java)

⬛ 프로그래머스 (PCCP) | LV.2 석유 시추 - BFS/DFS + 구현 문풀 (Java)

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

프로그래머스

문제 설명

문제 설명 2

---

💚문제 접근 방식

정확성과 효율성을 모두 통과해야 되는 문제이다.

일단 시추로 각 열에 대해 쭉 들어갔을 때 터치하는 석유 크기는 모두 합해야하는데, 중복되진 않게 세는 게 중요하다.

 

1) BFS로 land가 들어왔을 때 1로 찍힌 부분을 모두 진입하면서 연결된 덩어리 크기를 구하여 반환시킨다.

→ 처음에는 이걸 다시 BFS로 돌면서 해당 덩어리 크기를 갖는 애를 다시 방문하며 세팅할 생각을 했지만 그걸 2번씩 매번 도는 게 시간이 많이 쓰일 거 같았고 이 문제가 효율성도 중요하기 때문에 다른 방법을 택했다.

 

2) BFS 호출 시 세팅할 value로 index값을 매번 덩어리마다 다르게 세팅해서 각 덩어리를 구분시켜주었다.

 

3) BFS 가 반환해준 그 크기는 Map<Integer, Integer> 로 각 index(덩어리구분용 key) 에 대한 value 로서 세팅해준다.

 

4) 이제 각 열에 대하여 모든 행을 돌면서 쭉 진입했을 때 터치하는 덩어리를 봐야 되는데 중복되지 않도록 countMap 선언하여 진입한 덩어리를 분별되게 담도록 했다.

 

5) 담겨진 덩어리에서의 key를 꺼내서 이전 map에 있던 값을 꺼내고 sum ++ 처리하고 이 누적된 값을 최종 list에 세팅해서 해당 열로 진입 시 만날 덩어리 최종 누적값을 세팅했고 그 중 max인 값을 반환했다.

---

💚 제출 코드

import java.util.*;

class Solution {
    //4 방향 
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    //visited
    static boolean[][] visited;
    
    //BFS 탐색용 -> 해당 범위 val 반환용 
    static int BFS(int[][] land, int x, int y, int val){
        Queue<int[]> Q = new LinkedList<>();
        visited[x][y] = true;
        Q.offer(new int[] {x, y});
        land[x][y] = val;//세팅 
        int cnt = 1;
        while(!Q.isEmpty()){
            int[] cur = Q.poll();
            for(int k=0; k<4; k++){
                int nx = cur[0] + dx[k];
                int ny = cur[1] + dy[k];
                if(nx < 0 || nx >= land.length || ny <0 || ny >= land[0].length || visited[nx][ny] || land[nx][ny] == 0) continue;
                
                //유효하고 1인 값에 대하여 
                visited[nx][ny] = true;
                land[nx][ny] = val;//값 세팅 
                cnt++;
                Q.offer(new int[] {nx, ny});
            }
        }
        
        return cnt;
    }

    //솔루션 함수 
    public int solution(int[][] land) {
  
        visited = new boolean[land.length][land[0].length];
        
        int index = 10; 
        Map<Integer, Integer> map = new HashMap<>();
        
        //1) BFS 전범위 돌면서 1가진 값에 대한 value 얻어오기 
        for(int i=0; i<land.length; i++){
            for(int j=0; j<land[0].length; j++){
                if(!visited[i][j] && land[i][j] == 1){
                    int val = BFS(land, i, j, index); //얻은 점수 세팅을 
                    map.put(index, val);//해당 인덱스의 값을 val 로 세팅 
                    index++; //구분하기 위함 
                }
            }
        }
        
        List<Integer> list = new ArrayList<>();
        
        //만난 key에 대한 카운팅해서 식별용 
        Map<Integer, Integer> countMap;
        
        
        //각 열에 대한 모든 행에서의 합을 구할 거임 
        for(int i=0; i<land[0].length; i++){ //각 열에 대하여 
            countMap =  new HashMap<>();
            for(int j=0; j<land.length; j++){ //모든 행을 돌거임 
                if(land[j][i] == 0) continue;
                countMap.put(land[j][i], countMap.getOrDefault(land[j][i], 0) + 1);
            }
            
            int sum = 0;
            //탈출 후 
            for(int key : countMap.keySet()){
                sum += map.get(key);
            }
            list.add(sum);
        }
        
        int max = Integer.MIN_VALUE;
        for(int x : list){
            max = Math.max(x, max);
        }
        
        
        return max;
    }
}

---

💚 회고

좀 복잡했지만 생각한대로 풀이를 쭉 밀고 갔더니 잘 풀렸다. 다행이다.