[JAVA] 프로그래머스 level2 [PCCP 기출문제] 2번 / 석유 시추

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

프로그래머스

코딩테스트 연습 > PCCP 기출문제 > [PCCP 기출문제] 2번 / 석유 시추

 

문제 접근 

문제유형은 BFS + 구현 이다.

 

처음 문제를 풀 때는 각 열마다  BFS를 통해서 해당 열에 대한 시추선이 얻을  수 있는 석유의 합을 구했다.

 

해당 코드 

import java.util.*;
class Solution {
    static int [] arx = {-1,1,0,0};
    static int [] ary = {0,0,-1,1};
    static int row, col;
    static boolean [][] visited;
    static int max = 0;
    public int solution(int[][] land) {
       
        row = land.length; // 행 
        col = land[0].length; // 열
        for(int i = 0; i < col; i++){
            BFS(i, land);    
        }
        return max;
    }
    public static void BFS(int start, int [][] land){
        visited = new boolean [row][col];
        int sum = 0;
        ArrayDeque<int[]> q = new ArrayDeque<>();
        for(int i = 0; i < row; i++){
            if(visited[i][start] || land[i][start] == 0) continue;
            sum++;
            visited[i][start] = true;
            q.add(new int[]{i, start});
            while(!q.isEmpty()){
                int [] cur = q.poll();
                for(int j = 0; j < 4; j++){
                    int nx = cur[0] + arx[j];
                    int ny = cur[1] + ary[j];
                    if(!validation(nx, ny) || visited[nx][ny] || land[nx][ny] == 0) continue;
                    sum++;
                    visited[nx][ny] = true;
                    q.add(new int[]{nx,ny});
                }
            }
        }
        if(sum > max){
            max = sum;
        }
    }
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < row && ny < col) return true;
        return false;
    }
}

 

정확성 테스트는 모두 통과했지만 효율성 테스트에서는 전부 틀렸다. 

어떤 로직의 시간 복잡도를 개선할 수 있을까?

 

내가 생각한 방법은 각 석유 공간을 BFS를 통해서 구하고 이름과 크기를 붙이고 기록하는 방법이었다. 

그럼 같은 석유 공간을 또다시 BFS 할 필요 없다.

 

첫 번째 풀이는 각 열마다 겹치는 석유 영역을 계속 반복해서 BFS를 하고 있다. 

이 부분이 비효율적이었던 것이다.

 

첫 번째 방법(왼쪽)과 두 번째 방법(오른쪽) 각 석유 공간의 BFS 횟수 차이이다. 

 

정답 코드

import java.util.*;
class Solution {
    static int [] arx = {-1,1,0,0};
    static int [] ary = {0,0,-1,1};
    static int row, col;
    static boolean [][] visited;
    static int max = 0;
    static int [] memo;
    public int solution(int[][] land) {
        
        row = land.length; // 행 
        col = land[0].length; // 열
        int [][] after = BFS(land);
        
        for(int i = 0; i < col; i++){
            Set<Integer> set = new HashSet<>();
            for(int j = 0; j < row; j++){
                set.add(after[j][i]);
            }
            
            int sum = 0;
            Iterator<Integer> it = set.iterator();
            while(it.hasNext()){
                int next = it.next();
                sum += memo[next];
            }
            
            if(max < sum) max = sum;
        }
        
        
        return max;
    }
    public static int [][] BFS(int[][] land){
        boolean [][] visited = new boolean [row][col];
        int cnt = 0;
        Queue<int[]> q = new LinkedList<>();
        ArrayList<int[]> list = new ArrayList<>();
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(visited[i][j] || land[i][j] == 0) continue;
                cnt++;
                int sum = 1;
                land[i][j] = cnt;
                visited[i][j] = true;
                q.add(new int[]{i,j});
                while(!q.isEmpty()){
                    int [] cur = q.poll();
                    for(int k = 0; k < 4; k++){
                        int nx = cur[0] + arx[k];
                        int ny = cur[1] + ary[k];
                        if(!validation(nx,ny) || visited[nx][ny] || land[nx][ny] == 0) continue;
                        visited[nx][ny] = true;
                        land[nx][ny] = cnt;
                        sum++;
                        q.add(new int[]{nx,ny});
                    }
                }
                list.add(new int[]{cnt, sum});
            }
        }
        memo = new int[cnt+1];
        
        Iterator<int[]> it = list.iterator();
        while(it.hasNext()){
            int [] next = it.next();
            memo[next[0]] = next[1];
        }
        
        return land;
    }
    
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < row && ny < col) return true;
        return false;
    }
}