[프로그래머스 level2] 석유시추 자바 BFS

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

프로그래머스

문제

int[][] land는 땅의 정보이며 0은 빈 땅, 1은 석유를 의미함.

각 칼럼별로 시추하였을 때 최대 시추량은 얼마인지 구하시오.

 

접근

Map<Integer, Set<Integer>> 로 칼럼별로 존재하는 석유 위치를 저장하고 이를 활용하려 했음.
그러나 그 이후의 방법이 떠오르지 않음.

public int solution(int[][] land) {
        Map<Integer, Set<Integer>> oilMap = new HashMap<>();
        //칼럼별 석유 위치 정보가 필요함.
        for(int y = 0; y < land.length; y ++){
            for(int x = 0; x < land[y].length; x ++){
                if(land[y][x] == 1){
                    oilMap.computeIfAbsent(x, k-> new HashSet<>()).add(y);
                }
            }
        }
        return 0;
    }

피드백

덩어리 찾기와 같은 경우는 BFS, DFS 중 어떤 방식을 차용해도 무난하나,
통상적으로는 층별 탐색의 경우 BFS가 유리함.

---

구분BFS (너비 우선 탐색)DFS (깊이 우선 탐색)

구조	Queue 사용	Stack 또는 재귀 사용
탐색 순서	가까운 노드부터 넓게 퍼지며 탐색	한 방향으로 깊게 파고들며 탐색
구현 방식	큐에 넣고 꺼내면서 진행	재귀 함수 호출 or 스택 사용
사용 예	최단 거리, 레벨 탐색 등	경로 탐색, 백트래킹 등

---

코드

public int solution2(int[][] land) {
        int n = land.length;
        int m = land[0].length;

        boolean[][] visited = new boolean[n][m];
        Map<Integer, Integer> oilSizeMap = new HashMap<>();
        Map<Integer, Set<Integer>> oilColumnMap = new HashMap<>();
        int id = 1; // 석유 덩어리 id

        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};

        // 1. 모든 석유 덩어리 탐색
        for (int y = 0; y < n; y++) {
            for (int x = 0; x < m; x++) {
                if (land[y][x] == 1 && !visited[y][x]) {
                    Queue<int[]> q = new LinkedList<>();
                    q.offer(new int[]{y, x});
                    visited[y][x] = true;

                    int size = 0;
                    Set<Integer> columns = new HashSet<>();

                    while (!q.isEmpty()) {
                        int[] curr = q.poll();
                        int cy = curr[0], cx = curr[1];
                        size++;
                        columns.add(cx);
                        land[cy][cx] = id;

                        for (int d = 0; d < 4; d++) {
                            int ny = cy + dy[d];
                            int nx = cx + dx[d];

                            if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
                                if (land[ny][nx] == 1 && !visited[ny][nx]) {
                                    visited[ny][nx] = true;
                                    q.offer(new int[]{ny, nx});
                                }
                            }
                        }
                    }

                    oilSizeMap.put(id, size);
                    for (int col : columns) {
                        oilColumnMap.computeIfAbsent(col, k -> new HashSet<>()).add(id);
                    }

                    id++;
                }
            }
        }

        // 2. 칼럼마다 최대 시추량 계산
        int maxOil = 0;
        for (int x = 0; x < m; x++) {
            Set<Integer> oilIds = oilColumnMap.getOrDefault(x, new HashSet<>());
            int sum = 0;
            for (int oid : oilIds) {
                sum += oilSizeMap.get(oid);
            }
            maxOil = Math.max(maxOil, sum);
        }

        return maxOil;
    }

 

1.석유크기와 석유 칼럼을 각각 따로 매핑한다.
2.BFS방식으로  크기맵과 칼럼맵에 데이터를 저장한다.
3. 칼럼맵에 저장된 석유id들로 크기맵에서 꺼내 더한다.
   칼럼맵의 Set 길이가 가장 길다 == 여러 석유 덩어리를 한꺼번에 캘 수 있다.