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

프로그래머스

 

1. 제출 코드(1시간 28분 35초)

import java.util.*;

class Solution {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] visited;
    static int index = 2;
    
    public int solution(int[][] land) {
        int answer = 0;
        ArrayList<Integer> area = new ArrayList<>();
        visited = new boolean[land.length][land[0].length];
        
        // 구역 나누기
        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) {
                    visited[i][j] = true;
                    area.add(dfs(land, i, j, 1));
                    index++;
                }
            }
        }

        // 나눈 구역을 바탕으로 열마다 탐색하여 결과 값 추출
        for(int i = 0; i < land[0].length; i++) {
            int temp = 0;
            ArrayList<Integer> confirm = new ArrayList<>();
            for(int j = 0; j < land.length; j++) {
                if(land[j][i] != 0 && !confirm.contains(land[j][i])) {
                    temp += area.get(land[j][i] - 2);
                    confirm.add(land[j][i]);
                }
            }
            answer = Math.max(answer, temp);
        }
        return answer;
    }
    
    // DFS로 주변 구역 탐색
    static int dfs(int[][] land, int x, int y, int cnt) {
        land[x][y] = index;
            
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= land.length || nx < 0 || ny >= land[0].length || ny < 0 || visited[nx][ny] || land[nx][ny] == 0){
                continue;
            }
            visited[nx][ny] = true;
            cnt = dfs(land, nx, ny, cnt + 1);
        }
        return cnt;
    }
}

 

2. 실패 코드

class Solution {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] visited;
    
    public int solution(int[][] land) {
        int answer = 0;
        
        for(int i = 0; i < land[0].length; i++) {
            int temp = 0;
            visited = new boolean[land.length][land[0].length];
            for(int j = 0; j < land.length; j++) {
                if(!visited[j][i] && land[j][i] == 1) {
                    visited[j][i] = true;
                    temp += dfs(land, j, i, 1);
                }
            }
            answer = Math.max(answer, temp);
        }
        return answer;
    }
    
    static int dfs(int[][] land, int x, int y, int cnt) {
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= land.length || nx < 0 || ny >= land[0].length || ny < 0 || visited[nx][ny] || land[nx][ny] == 0){
                continue;
            }
            visited[nx][ny] = true;
            cnt = dfs(land, nx, ny, cnt + 1);
        }
        return cnt;
    }
}

 

 

3. 유의할 점

• 실패 코드를 보면 시추관을 하나 삽입할 때마다 DFS를 중복해서 돌리고 있었다. 이로 인해 효율성 체크해서 통과하지 못했다.
• 그래서 DFS를 처음부터 끝까지 돌려놓고 그 값을 저장해 놓았다. 그리고 시추를 삽입하여 해당 범위의 석유 값을 가져와 정답을 구하는 방식으로 풀이를 진행했다.
• 시간 복잡도를 고려해서 매 풀이마다 효율성을 체크하는 습관을 들여야겠다.
• 시간도 꽤 걸려서 풀었는데 시간 복잡도를 고려하지 않고 중간에 한 번 헤매서 그런 거 같다.