[알고리즘 TIL] 석유 시추

문제

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

프로그래머스

프로그래머스 LV2. DFS

설명

전형적인 DFS 문제이다. 하지만, 열(컬럼)마다 덩어리 크기의 합을 구해야하므로 약간의 응용이 필요했다.

나는 HashSet과 HashMap을 이용해 방문한 컬럼에 해당 덩어리 크기를 더해서, 마지막에 모든 컬럼을 돌면서 덩어리의 합 최댓값을 구했다.

구현

import java.util.*;

public class Q_석유시추_DFS {

    static boolean[][] visited;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {-1, 1, 0, 0};
    static int N;
    static int M;
    static HashMap<Integer, Integer> map;

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] land = new int[][]{
                {0, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 1, 1, 0, 0},
                {1, 1, 0, 0, 0, 1, 1, 0},
                {1, 1, 1, 0, 0, 0, 0, 0},
                {1, 1, 1, 0, 0, 0, 1, 1}};
        int answer = solution.solution(land);
        System.out.println(answer);
    }

    static class Solution {
        public int solution(int[][] land) {
            int answer = 0;
            N = land.length;
            M = land[0].length;
            visited = new boolean[N][M];
            map = new HashMap<>();

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (visited[i][j] || land[i][j] == 0) continue;
                    dfs(land, i, j);
                }
            }

            for (Integer key : map.keySet()) {
                if (map.get(key) > answer) answer = map.get(key);
            }
            return answer;
        }

        private void dfs(int[][] land, int row, int col) {
            Stack<Integer[]> stack = new Stack<>();
            stack.push(new Integer[]{row, col});
            int count = 0;
            Set<Integer> cols = new HashSet<>();

            while (!stack.isEmpty()) {
                Integer[] pop = stack.pop();
                int y = pop[0];
                int x = pop[1];

                if (visited[y][x]) continue;
                visited[y][x] = true;
                count++;
                cols.add(x);

                for (int i = 0; i < 4; i++) {
                    int nextY = y + dy[i];
                    int nextX = x + dx[i];

                    if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N || visited[nextY][nextX] || land[nextY][nextX] == 0)
                        continue;
                    stack.push(new Integer[]{nextY, nextX});
                }
            }

            for (Integer setCol : cols) {
                if(map.containsKey(setCol)) map.put(setCol, map.get(setCol) + count);
                else map.put(setCol, count);
            }
        }
    }

}