Algorithm/src/programmers/lv2/Programmers_250136.java at main · DevJake88/Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package programmers.lv2;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Programmers_250136 {
    public static void main(String[] args) {
        Programmers_250136 test = new Programmers_250136();
        int[][] land = {
                { 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 result = test.solution(land);
        System.out.println("result: " + result);
    }

    public int solution(int[][] land) {
        int answer = 0;
        int N = land.length; // 세로
        int M = land[0].length; // 가로

        // 1. 덩어리별로 ID를 줘서 맵에 표시하기 & 크기 측정
        boolean[][] visited = new boolean[N][M];
        int id = 1;
        int[][] mapId = new int[N][M];
        ArrayList<Integer> sizeList = new ArrayList<>();
        for (int j = 0; j < M; j++) {
            for (int i = 0; i < N; i++) {
                if (land[i][j] == 1 && !visited[i][j]) {
                    // int size = dfs(i, j, land, visited, mapId, id);
                    int size = bfs(i, j, land, visited, mapId, id);
                    sizeList.add(size);
                    id++;
                }
            }
        }

        // 2. 시추를 뚫는 곳 확인
        for (int j = 0; j < M; j++) {
            HashSet<Integer> hs = new HashSet<>();
            int sizeSum = 0;
            for (int i = 0; i < N; i++) {
                if (land[i][j] == 1 && mapId[i][j] > 0 && !hs.contains(mapId[i][j])) {
                    hs.add(mapId[i][j]);
                    sizeSum += sizeList.get(mapId[i][j] - 1);
                }
            }
            answer = Math.max(answer, sizeSum);
        }

        return answer;
    }

    public int bfs(int r, int c, int[][] land, boolean[][] visited, int[][] mapId, int id) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] { r, c });
        visited[r][c] = true;
        mapId[r][c] = id;
        int size = 1;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int[][] pos = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; // 상하좌우
            for (int i = 0; i < pos.length; i++) {
                int nr = cur[0] + pos[i][0];
                int nc = cur[1] + pos[i][1];

                if (nr >= 0 && nr < land.length && nc >= 0 && nc < land[0].length && land[nr][nc] == 1
                        && !visited[nr][nc]) {
                    queue.add(new int[] { nr, nc });
                    visited[nr][nc] = true;
                    mapId[nr][nc] = id;
                    size++;
                }
            }

        }
        return size;
    }

    /*
     * 맵이 500*500 이라 재귀로 하면 250,000 번의 재귀가 실행될 수 있으므로 스택오버플로우 발생할 수 있다.
     * public int dfs(int r, int c, int[][] land, boolean[][] visited, int[][]
     * mapId, int id) {
     * int count = 1;
     * visited[r][c] = true;
     * mapId[r][c] = id;
     * int[][] pos = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; // 상하좌우
     * for (int i = 0; i < pos.length; i++) {
     * int nr = r + pos[i][0];
     * int nc = c + pos[i][1];
     *
     * if (nr >= 0 && nr < land.length && nc >= 0 && nc < land[0].length &&
     * land[nr][nc] == 1
     * && !visited[nr][nc]) {
     * count += dfs(nr, nc, land, visited, mapId, id);
     * }
     * }
     * return count;
     * }
     */
}