프로그래머스 - 석유시추

 

구현 1차 절망, 시간복잡도 2차 절망이었다.

 

처음에는 그냥 bfs + visited로 해서 열마다 방문 횟수 초기화를 해주면서 계속 돌렸는데, 정답은 구할 수 있지만 효율성 테스트에서 전부 시간 초과가 나왔다.

 

그래서 생각한 건 방문 횟수 초기화를 하지 말고 모든 그래프를 돌며 수행한 bfs의 결과를 배열로 만들어서

[left, right, count] 전체 열을 돌면서 이중 배열을 만들어주고

전체 열만 돌면서 left <= col && right >= col 인 경우 count++ 를 해주고 나온 값의 max를 리턴해줬다.

이렇게 하니까 시간복잡도는 줄일 수 있었는데 문제 2,3 번에서는 시간초과가 나왔다. 

 

 

그러다가 생각난 게 굳이 배열을 만들어서 for문을 돌릴 필요 없이 저 배열 하나를 add 하는 대신 처음에 전체 열의 count를 세는 Array를 만들어주고 거기다가 더해주면 될 것 같았다. 그렇게 했고 성공했다.

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Arrays;

class Solution {
  static int[][] graph;
    static boolean[][] visited;
    static int[] counts;
    static int[][] directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static void initialize(int[][] land) {
        int n = land.length + 2;
        int m = land[0].length + 2;
        graph = new int[n][m];
        visited = new boolean[n][m];

        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < m - 1; j++) {
                graph[i][j] = land[i-1][j-1];
            }
        }
    }

    // 첫 인덱스 끝 인덱스 카운트
    public static void bfs(int n, int m) {
        Queue<int[]> q = new LinkedList<>();
        int count = 0;
        int left = Integer.MAX_VALUE;
        int right = Integer.MIN_VALUE;
        q.add(new int[]{n, m});
        visited[n][m] = true;
        count++;
        while (!q.isEmpty()) {
            int[] now = q.poll();
            left = Math.min(now[1], left);
            right = Math.max(now[1], right);
            for (int[] direction : directions) {
                if (!visited[now[0] + direction[0]][now[1] + direction[1]] && graph[now[0] + direction[0]][now[1] + direction[1]] == 1) {
                    q.add(new int[]{now[0] + direction[0], now[1] + direction[1]});
                    visited[now[0] + direction[0]][now[1] + direction[1]] = true;
                    count++;
                    left = Math.min(now[1] + direction[1], left);
                    right = Math.max(now[1] + direction[1], right);
                }
            }
        }
        for(int i = left; i <= right; i++) {
            counts[i] += count;
            // counts[i] 번의 value의 경우 solution을 돌면서 아래에도 석유가 있을 경우
            // 추가가 될 수도 있다.
        }
    }
    public static int solution(int[][] land) {
        initialize(land);
        counts = new int[land[0].length+1];
        
        for(int j = 1; j < land[0].length+1; j++) {
            for(int i = 1; i < land.length+1; i++) {
                if(graph[i][j] == 1 && !visited[i][j]) {
                    bfs(i,j);
                }
            }
        }

        return Arrays.stream(counts).max().getAsInt();
    }
}