[프로그래머스] 석유 시추- JAVA(자바)

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

프로그래머스

풀이:

처음에는 각 열에 대해서 땅을 하나씩 내려가면서 총 석유량을 구했지만 중복되는 bfs 때문에 time-out이 발생했다.

석유 덩어리를 찾고 그 위치를 기억하면 중복되는 bfs를 하지 않아도 된다.

bfs를 할 때 방문한 땅의 y좌표를 set에 저장해 두면 그 석유덩어리가 차지하는 y좌표들을 저장할 수 있다. 그리고 그 oils 배열에 그 y좌표에 해당하는 곳에 bfs로 구한 총 석유량을 누적해서 더하면 최종으로 각 열마다 발견할 수 있는 총 석유량을 알 수 있다.

 

코드:

import java.util.*;

class Solution {

    int n, m;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, -1, 0, 1};
    int[] oils; // oils[i]: i+1 열에 시추관을 설치했을 때 얻을 수 있는 석유량

    boolean[][] visited;
    public int solution(int[][] land) {
        n = land.length;
        m = land[0].length;
        oils = new int[m];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (land[i][j] == 0 || visited[i][j]) continue;
                bfs(i, j, land);
            }
        }

        return Arrays.stream(oils).max().getAsInt();
    }
    public void bfs(int x, int y, int[][] land) {
        Queue<Pair> q = new LinkedList<>();
        Set<Integer> set = new HashSet<>(); // 한 덩어리의 석유가 위치하는 열(y)들의 집합
        q.add(new Pair(x, y));
        visited[x][y] = true;
        int sum = 1;

        while (!q.isEmpty()) {
            Pair cur = q.poll();
            set.add(cur.y); // 현재 땅의 열(y) 위치를 set에 저장
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if(land[nx][ny] == 0 || visited[nx][ny]) continue;
                sum++;
                visited[nx][ny] = true;
                q.add(new Pair(nx, ny));
            }
        }
        
        for (Integer col : set) {
            oils[col] += sum;
        }
    }
}

 class Pair{
    int x, y;

     public Pair(int x, int y) {
         this.x = x;
         this.y = y;
     }
 }