[프로그래머스] 석유 시추(Java)

문제

프로그래머스

풀이

이 문제는 열 별로 2차원 배열을 탐색하면서 연결 요소의 크기를 찾는 문제인데

N과 M이 각 500이기 때문에 2차원 배열을 모두 탐색하면서 BFS를 돌게되면 시간초과가 발생한다.

 

2차원 배열 순회는 반드시 해야하는 부분이므로

BFS 탐색을 줄일 수 있는 방안을 찾아야 한다.

 

여러 방법이 있겠지만, 문제를 풀며 떠오른 방법은

visit 배열을 전역으로 선언하고

BFS를 돌며 연결 요소 내의 원소의 개수(= 집합내의 원소의 개수)가 파악이 되면

집합 내 원소들의 열 좌표를 바탕으로 집합 내의 원소의 개수를 메모이제이션을 하는 방식으로 해결했다.

위 그림(시작점은 1.1)에서 첫번째 열에서 찾을 수 있는 집합의 좌표는 다음과 같다.

(3.1) (3,2)

(4,1) (4,2) (4,3)

(5,1) (5,2) (5,3)

 

이 값들의 열을 기준(1, 2, 3)으로 집합 내의 원소의 개수(8)을 메모이제이션 한다.

memo = [8, 8, 8, 0, 0, 0]와 같이 나타내어진다.(편의상 0번째 인덱스 무시)

이때, memo에 저장된 값에 현재 집합 내의 원소의 개수를 더해서 저장해주어야 함(하나의 집합만 저장하는 것이 아니기 때문)

 

이런 연산을 열의 개수만큼 해주면 답이 도출된다.

코드

import java.util.*;

class Solution {
    static boolean[][] v;
    static int[][] map;
    static int[] memo;
    static int N, M, cnt, ans;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    public int solution(int[][] land) {
        M = land[0].length;
        N = land.length;
        ans = 0;
        
        map = land;
        memo = new int[M];
        v = new boolean[N][M];
        
        for(int j = 0 ; j < M ; j ++){
            
            for(int i = 0 ; i < N ; i ++){
                if(v[i][j] || map[i][j] == 0) continue;
                bfs(i, j);
            }
        }
        int ans = 0;
        for(int i = 0 ; i < M ; i ++)
            ans = Math.max(ans, memo[i]);
        
        return ans;
    }
    static int bfs(int sr, int sc){
        Queue<int[]> q = new ArrayDeque<>();
        Set<Integer> set = new LinkedHashSet<>();
        q.offer(new int[] {sr, sc});
        v[sr][sc] = true;
        int cnt = 1;
        
        while(!q.isEmpty()){
            int[] cur = q.poll();
            set.add(cur[1]);
            
            for(int d = 0 ; d < 4 ; d ++){
                int nr = cur[0] + dr[d];
                int nc = cur[1] + dc[d];
                
                if(!isValid(nr, nc) || map[nr][nc] == 0 || v[nr][nc]) continue;
                
                v[nr][nc] = true;
                cnt ++;
                q.offer(new int[] {nr, nc});
            }
        }
        
        for(int cur: set)
            memo[cur] += cnt;
        
        return cnt;
    }
    static boolean isValid(int nr, int nc){
        return (nr>=0 && nr<N && nc>=0 && nc<M);
    }
}