[Programmers] [PCCP 기출문제] 2번 / 석유 시추 <JAVA>

문제

세로길이가 n, 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

시추관은 세로로 들어온다...

뚫으면서 시추 가능한 OIL 덩어리의 최대값을 구하는 문제..

그림 예시)
1 -> 8
2 -> 8
3 -> 8
4 -> 7
5 -> 7
6 -> 7
7 -> 7 + 2 => 9
8 -> 2

접근!

덩어리마다 ID 를 부여하는 방식?

그리고 id 마다 크기를 HashMap에 저장?

<Id, Size> {1,8} , {2,7} , {3,2}

세로로 시추관 뚫으면서 oil 인 경우 Map 과 비교후 저장?

psuedo code

for 행
    for 열
        if 방문 x and 기름
            size = bfs(Land, 행, 열, ID)
            Map.put(ID++, size)

bfs 코드

bfs(Land, 행, 열, ID) {
    queue 생성
    q <- 행, 열 

    방문처리 = true
    int size = 1 // 처음 크기는 1로 스타트
       land_ID[][] = ID; // id 로 저장

    while !q.isEmpty
        for loop
            동서남북 Search
            if 탐색 가능하고 방문 안했고 기름이면
                size++;

    return size;
}

덩어리 합 구하는 코드

//세로로 탐색하기 때문에 행 열 반대로 ~
for 열 {
    Set<Integer> set -> Id를 저장하는 Set
    int MAX = 0;
    for 행 {
        if (해당 칸이 1(석유)라면 ) {
            Set에 해당 좌표의 Id를 저장
        }
    }
    for (Set의 ID) {

        MAX += 오일크기를 담은 MAP.get(id)
    }
    answer = Math.max(maxOil, sum)
}

이 부분이 좀 헷갈렸다. 더 쉬운 방법은 없는지 계속 생각했고
결국 set을 계속 초기화 해주면서 기름을 찾으면 그에 해당하는 size 를 더해가면서 진행했다.

전체 코드

import java.util.*;

class Solution {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int[][] landId; // 덩어리를 담을 map
    static boolean[][] visited;
    static int rows,cols;
    static HashMap<Integer,Integer> oil_info = new HashMap<>();
    public int solution(int[][] land) {
        int answer = 0;

        rows = land.length;
        cols = land[0].length;

        landId = new int[rows][cols];
        visited = new boolean[rows][cols];

        int oil_index = 1;
        for(int i=0; i<rows; i++) {
            for(int j=0;j<cols;j++){
                if(!visited[i][j] && land[i][j] == 1){
                    //bfs 시작
                    int size = bfs(land,i,j,oil_index); //rows, cols
                    oil_info.put(oil_index++,size);
                }
            }
        }
        for(int i=0; i<cols; i++) {
            HashSet<Integer> set = new HashSet<>();
            int temp = 0;
            for(int j=0; j<rows; j++) {
                if(land[j][i] == 1) {
                    set.add(landId[j][i]);
                }
            }

            for(Integer oil : set) {
                temp += oil_info.get(oil);
                System.out.println(temp);
            }
            answer = Math.max(temp,answer);

        }


        return answer;
    }

    private int bfs(int[][] land, int n, int m, int oil_index) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {n,m});

        visited[n][m] = true;
        landId[n][m] = oil_index;

        int oil_size = 1;

        while(!q.isEmpty()) {
            int[] pos = q.poll();

            for(int i=0; i<4; i++) {
                int nx = pos[0] + dx[i];
                int ny = pos[1] + dy[i];

                if(nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
                    if(!visited[nx][ny] && land[nx][ny] == 1) {
                        q.offer(new int[] {nx,ny});
                        landId[nx][ny] = oil_index;
                        visited[nx][ny] = true;
                        oil_size++;
                    }
                }
            }
        }
        return oil_size;
    }
}

재밌게 풀었다. 덩어리 합 구하는 부분에서 좀 막히긴 했지만 어찌저찌 해결해 나간듯하다.