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

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

프로그래머스

 

bfs로 풀면 될 것이다.

import java.util.*;
class Solution {
    public int [] dx = {0,0,-1,1};
    public int [] dy = {1,-1,0,0};
    public int solution(int[][] land) {
        int answer = 0;
        for(int i = 0; i < land[0].length; i++) {
            answer = Math.max(bfs(i, land), answer);
        }
        return answer;
    }
    private int bfs(int m, int[][] land) {
        int result = 0;
        boolean[][] visited = new boolean[land.length][land[0].length];
        Queue<int[]> q = new LinkedList<>();
        for(int i = 0; i < land.length; i++) {
            if(visited[i][m]) continue;

            if(land[i][m] == 1) {
                visited[i][m] = true;
                q.offer(new int[]{i , m});
            }

            while(!q.isEmpty()) {
                int[] currQ = q.poll();
                int currX = currQ[0];
                int currY = currQ[1];
                result++;

                for(int j = 0; j < 4; j++) {
                    int x = currX + dx[j];
                    int y = currY + dy[j];
                    if(x >= 0 && y >= 0 && x < land.length && y < land[0].length && !visited[x][y] && land[x][y] == 1) {
                        visited[x][y] = true;
                        q.offer(new int[]{x, y});
                    }
                }
            }

        }

        return result;
    }
}

 

효율성 테스트에서 시간 초과가 났다.

이미 파악된 석유덩어리의 크기를 따로 저장해서 그 석유 덩어리를 만난다면 순회하지 않고 계산해주면 될 것 같다.

(귀찮아서 이만..)