[프로그래머스][JAVA] 석유 시추

링크

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

프로그래머스

 

 

---

정리

 

실패 코드

 

dfs 로 하려고 시도했으나 실패하였다.

각 열 기준으로 하나씩 검사하면서 있는 것은 visited 체크를 해주면서 합계를 구한다.

하나의 열을 다 돌면 합계를 구한다.

 

정확성은 성공했으나 효율성에서 실패. 

중간부터 실패할 것이라 감은 왔으나 다른 방법이 딱히 생각나지 않았기에 진행하였음.

 

성공 코드

 

bfs로 처리한 다음 어떻게 효율적으로 처리할 것인지가 중요했다.

 

각 칸 기준으로 하나씩 검사하면서 있는 것은 oil을 조사한 것으로 체크하고 0으로 만든다. 

예를 들어서 0,1,2 열에 8칸 짜리가 있었다면 oilColSum[0] = 8 , oilColSum[1] = 8, oilColSum[2] = 8 이런 식으로 저장해버리는 것이다.

이미 0으로 되어 있는 것은 다음 bfs 때는 bfs 자체를 안해도 된다.

 

필요 없는 것은 아예 다음 queue에서 처리하지 않도록 해버리는 것이 포인트였다. (효율성 극대화를 위함)

---

 

풀이

실패 코드

class Solution {
    // 상, 하, 좌, 우
    static int[] dx = new int[]{0, 0, -1, 1};
    static int[] dy = new int[]{-1, 1, 0, 0};
    static int oilSum = 0;
    
    public int solution(int[][] land) {
        int answer = 0;
        int n = land.length;
        int m = land[0].length;
        int[][] oilMap = new int[n][m];
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                oilMap[i][j] = land[i][j];
            }
        }
        
        // 각 칸마다 찾아가면서 dfs를 한다.
        // 정점 visited 된 것은 표시를 해 다시 할 필요가 없게한다.
        // 0 이상인 것은 이미 한 것으로 취급한다.
        // 합계의 max 값을 구한다.
        for (int i=0; i<m; i++) {
            int oilColSum = 0;
            boolean[][] oilVisitedMap  = new boolean[n][m];
            for (int j=0; j<n; j++) {
                // 방문 맵 초기화
                int cx = j;
                int cy = i;
                oilSum = 0;
                dfs(oilMap, cx, cy, n, m, oilVisitedMap);
                oilColSum += oilSum;
            }
            
            answer = Math.max(oilColSum, answer);
        }
        
        return answer;
    }
    
    public static void dfs(int[][] oilMap, int cx, int cy, int n, int m, boolean[][] oilVisitedMap) {
        // 예외 조건
        if (cx < 0 || cy < 0 || cx >= n || cy >= m) {
            return;
        }
        if (oilVisitedMap[cx][cy]) {
            return;
        }
        if (oilMap[cx][cy] == 0) {
            return;
        }
        // 방문 체크 및 sum
        if (!oilVisitedMap[cx][cy] && oilMap[cx][cy] == 1) {
            oilVisitedMap[cx][cy] = true;
            oilSum++;
            // System.out.println("x : " + cx + ", y : " + cy);
            // System.out.println(oilSum);
        }
        
        // dfs
        for (int k=0; k<4; k++) {
            int nx = cx + dx[k];
            int ny = cy + dy[k];
            dfs(oilMap, nx, ny, n, m, oilVisitedMap);
        }
    }
}

 

성공 코드

 

import java.util.*;

class Solution {
    // 상, 하, 좌, 우
    static int[] dx = new int[]{0, 0, -1, 1};
    static int[] dy = new int[]{-1, 1, 0, 0};
    static Set<Integer> colNums;
    static int[] oilColSums;
    
    public int solution(int[][] land) {
        int answer = 0;
        int n = land.length;
        int m = land[0].length;
        int[][] oilMap = new int[n][m];
        oilColSums = new int[m];
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                oilMap[i][j] = land[i][j];
            }
        }
        
        // 각 칸마다 찾아가면서 bfs를 한다.
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                int cx = j;
                int cy = i;
                if (oilMap[cx][cy] == 0) continue;
                colNums = new HashSet<>();
                bfs(oilMap, cx, cy, n, m);
            }
        }
        
        for (int oilColSum : oilColSums) {
            answer = Math.max(answer, oilColSum);
        }
        
        return answer;
    }
    
    public static void bfs(int[][] oilMap, int sx, int sy, int n, int m) {
        Queue<int[]> queue = new LinkedList<>();
        // 각 열 정보를 저장하고 마지막 count를 다 열 석유 합계 정보에 더해준다.
        queue.add(new int[]{sx, sy});
        int oilSum = 0;
        oilMap[sx][sy] = 0;
        colNums.add(sy);
        oilSum++;
        
        while(!queue.isEmpty()) {
            int[] point = queue.poll();
            int cx = point[0];
            int cy = point[1];

            for (int k=0; k<4; k++) {
                int nx = cx + dx[k];
                int ny = cy + dy[k];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m || oilMap[nx][ny] == 0) {
                    continue;
                }
            
                if (oilMap[nx][ny] == 1) {
                    oilMap[nx][ny] = 0;
                    colNums.add(ny);
                    oilSum++;
                }
                
                queue.add(new int[]{nx, ny});
            }
        }
        
        for (int colNum : colNums) {
            oilColSums[colNum] += oilSum;
        }
    }
}