Lv 2. 석유 시추

 

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

프로그래머스

 

 

 

이번 문제는 석유 시추관을 2차원 배열상에서 내렸을때 마주하는 최대 석유 매장량을

구하는 문제이다.

 

이 문제를 풀기위해 2가지 class를 따로 정의 하였다.

Node class를 통해서 좌표 class 를 정의하여 bfs 탐색을 원활하게 하고자 하였고

Oil class를 통해서 석유 매장량을 체크하고 최소 몇의 y좌표에 내렸을때 마주할 수 있는지

최대 몇의 y좌표에서 시추관을 내렸을때 마주할 수 있는지를 확인할 수 있게 하였다.

 

int[][] dir 를 선언하여 4방향 탐색이 가능하게 하였고

Queue q 를 선언하여 bfs 탐색의 필수 자료구조 queue를 선언하였다.
boolean[][] isVisited 를 선언하여 중복 탐색을 방지하였다.

 

i가 0 에서 N 까지 j가 0에서 M 까지 순회하면서 처음 석유를 발견하게 되면 그 석유좌표를 기준으로 bfs 메서드에서 연결된 석유들을 탐사하게 된다.

그리고 ArrayList<Oil> list에 석유들이 저장되어 추후 y좌표별 탐색시 용이하게 한다.

 

bfs 메서드가 끝나게 되면 y좌표의 범위 0에서 M까지 순회하면서

list에 존재하는 모든 Oil들을 탐색하여 이 y좌표에서 발견되는지 Oil의 start, end 를 통해

확인후 count에 증가시키고, 모든 Oil들을 순회 완료 하였다면

answer 에서 최댓값 비교를 통해 정답을 찾아낸다.

 

 

import java.util.*;
import java.io.*;

class Solution {
    class Oil{
        int start;
        int end;
        int size;
        public Oil(int start,int end, int size){
            this.start = start;
            this.end = end;
            this.size = size;
        }
    }
    class Node{
        int x;
        int y;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    
    ArrayList<Oil> list = new ArrayList<>();
    boolean[][] isVisited;
    int N,M;
    int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};
    
    
    void bfs(int x, int y, int[][] land){
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(x,y));
        isVisited[x][y] = true;
        int count = 1, minY = y, maxY = y;
        while(!q.isEmpty()){
            Node node = q.poll();
            for(int d = 0; d < 4; d++){
                int dx = node.x+dir[d][0];
                int dy = node.y+dir[d][1];
                if(dx >= 0 && dx < N && dy >= 0 && dy < M &&
                  !isVisited[dx][dy] && land[dx][dy] == 1){
                    count++;
                    q.add(new Node(dx,dy));
                    isVisited[dx][dy] = true;
                    minY = Math.min(minY,dy);
                    maxY = Math.max(maxY,dy);
                }
            }
        }
        list.add(new Oil(minY,maxY,count));
    }
    
    public int solution(int[][] land) {
        N = land.length;
        M = land[0].length;
        isVisited = new boolean[N][M];
        
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < M ; j++){
                if(!isVisited[i][j] && land[i][j]==1){
                    bfs(i,j,land);
                }
            }
        }
        int answer = 0;
        for(int i = 0 ; i < M ; i++){
            int cnt = 0;
            for(int j = 0 ; j < list.size(); j++){
                Oil o = list.get(j);
                if(o.start <= i && o.end >= i)
                    cnt += o.size;
            }
            answer = Math.max(answer,cnt);
        }
        return answer;
    }
}