[Programmers] PCCP 기출문제 2번 - 석유 시추 - Java

문제

프로그래머스

 

풀이

여기에서 세로로 시추를 해서, 세로로 인접한 면에 있는 석유를 시추할때, 최대 석유 시추량을 구하는 문제이다.

나는 bfs를 이용해서 석유를 시추하는 덩어리(영역)마다 번호와 시추하는 양을 기록해야한다고 생각했다. 단 석유가 land 배열에서 1의 값을 가지기 때문에 2부터 시작하는 값을 영역의 번호를 매길 수 있다고 생각했다.

최악의 경우 영역의 번호가 제일 큰 경우 약 120000 값을 가지기 때문에, int로 해도 된다.

 

1. 위치에 대한 클래스(Point)를 만든다.

 

2. 석유 시추량을 담을 배열, 방문 여부 배열, 석유가 담겨 있는 상태에 대한 배열을 초기화한다.

시추량(amount)

방문 여부(visited)

석유 담겨 있는 상태(map)

 

3. 방문 되지 않았으면서, 석유가 있으면 세로운 영역이므로, bfs를 수행한다.

bfs를 수행하면서, 순회했던 점들을 ArrayList에 담는다.

bfs 수행이 끝나면, 순회했던 점들에 시추량과, 석유가 담겨 있는 상태에 영역 번호를 기록한다.

 

4. 세로로 map을 순회하면서, 영역의 번호가 다르면, 석유 시추 총량을 구해서 최대 시추량을 구한다.

이전 영역 int 변수가 아닌 set을 사용한 이유는 int 변수를 사용하면, 같은 영역이 겹치게 담길 수 있기 때문이다.

ㄷ자로 석유가 담겨 있다고 생각해보면 된다.

 

소스코드

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;

class Solution {
    private static class Point {
        int x;
        int y;
        
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    private static int n, m, areaNumber;

    private static int[][] map;
    private static int[][] amount;
    private static boolean[][] visited;
    
    private static int[] dx = {1, -1, 0, 0};
    private static int[] dy = {0, 0, 1, -1};
    
    public int solution(int[][] land) {
        m = land[0].length;
        n = land.length;
        areaNumber = 2;
        
        amount = new int[n][m];
        visited = new boolean[n][m];
        
        map = land;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    bfs(i, j, areaNumber++);
                }
            }
        }
        
        int answer = Integer.MIN_VALUE;
        
        for (int i = 0; i < m; i++) {
            int sum = 0;
            HashSet<Integer> set = new HashSet<>();
            
            for (int j = 0; j < n; j++) {
                if (!set.contains(map[j][i])) {
                    sum += amount[j][i];
                    
                    set.add(map[j][i]);
                }
            }
            
            answer = Math.max(sum, answer);
        }
        
        return answer;
    }
    
    private static void bfs(int sx, int sy, int areaNumber) {
        ArrayDeque<Point> queue = new ArrayDeque<>();
        ArrayList<Point> pointList = new ArrayList<>();
        
        queue.addLast(new Point(sx, sy));
        visited[sx][sy] = true;
        
        while (!queue.isEmpty()) {
            Point cur = queue.removeFirst();
            
            pointList.add(cur);
            
            for (int i = 0; i < 4; i++) {
                int mx = cur.x + dx[i];
                int my = cur.y + dy[i];
                
                if (mx < 0 || mx >= n || my < 0 || my >= m) continue;
                
                if (map[mx][my] == 1 && !visited[mx][my]) {
                    queue.addLast(new Point(mx, my));
                    visited[mx][my] = true;
                }
            }
        }
        
        int sum = pointList.size();
        
        for (Point p : pointList) {
            amount[p.x][p.y] = sum;
            map[p.x][p.y] = areaNumber;
        }
    }
}

 

실행결과