[프로그래머스] 석유 시추(Java)

문제 풀이

프로그래머스 석유 시추 문제입니다. 문제 출처

(1) 문제 파악

이어져 있는 석유의 개수를 파악하고 열에 걸쳐있는 석유를 모두 더했을 때 최댓값을 구하는 문제입니다.

(2) 문제 풀이 방법 생각하기

가장 먼저 이어져있는 석유 칸의 개수가 몇 개씩인지 파악해야 합니다. -> 그래프 탐색

이후 모든 열을 돌며 최대 석유의 값을 계산하면 됩니다. 그러나 모든 구역을 다 탐색해서 석유의 개수를 찾고, 또 전부 다 탐색해서 최대값을 계산하면 효율성 테스트에서 실패가 나옵니다.

그렇기 때문에 저는 bfs로 이어져 있는 석유의 개수를 구한 뒤에 어떤 열에 속해있는지를 따로 저장해두고, 나중에 열을 돌며 최댓값을 탐색할 때에는 저장된 값만 불러와서 더해주는 방식으로 문제를 풀어주면 됩니다!

(4) 구현

import java.util.*;

class Solution {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Map<Integer, List<Integer>> map;
    
    public int solution(int[][] land) {
        map = new HashMap<>();
        for(int i=0; i<land[0].length; i++) {
            map.put(i, new ArrayList<>());
        }
        
        for(int i=0; i<land.length; i++) {
            for(int j=0; j<land[0].length; j++) {
                if(land[i][j] == 1) {
                    bfs(land, i, j);
                }
            }
        }
        
        int answer = Integer.MIN_VALUE;
        for(int i=0; i<land[0].length; i++) {
            int count = 0;
            for(int n: map.get(i)) {
                count+=n;
            }
            answer = Math.max(count, answer);
        }

        return answer;
    }
    
    public void bfs(int[][] land, int x, int y) {
        Set<Integer> set = new HashSet<>();
        
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y));
        
        int count = 0;
        land[x][y] = -1;
        set.add(y);
        
        while(!q.isEmpty()) {
            Node now = q.poll();    
            count++;
            
            for(int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx<0 || ny<0 || nx>=land.length || ny>=land[0].length) continue;
                if(land[nx][ny] == 1) {
                    set.add(ny);
                    land[nx][ny] = -1;
                    q.offer(new Node(nx, ny));
                }
            }
        }

        for(int n: set) {
            map.get(n).add(count);
        }
    }
}

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