Repository navigation
Expand file tree
/
Copy pathSolution_PCCP_기출_2번_석유_시추.java
More file actions
70 lines (55 loc) · 1.7 KB
/
Copy pathSolution_PCCP_기출_2번_석유_시추.java
File metadata and controls
70 lines (55 loc) · 1.7 KB
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
package algorithm.programmers.Java;
import java.util.*;
public class Solution_PCCP_기출_2번_석유_시추 {
static int[][] landMap;
static int[] dr = {-1, 0, 1, 0};
static int[] dc = {0, 1, 0, -1};
static int N, M, labal;
static Map<Integer, Integer> map;
public int solution(int[][] land) {
int answer = 0;
N = land.length;
M = land[0].length;
landMap = land;
map = new HashMap<>();
labal = 2;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(landMap[i][j] != 1) continue;
bfs(i, j);
}
}
for(int i = 0; i < M; i++) {
Set<Integer> set = new HashSet<>();
for(int j = 0; j < N; j++) {
if(landMap[j][i] == 0) continue;
set.add(landMap[j][i]);
}
int sum = 0;
for(int labal : set) {
sum += map.get(labal);
}
answer = Math.max(answer, sum);
}
return answer;
}
static void bfs(int r, int c) {
int cnt = 0;
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[] {r, c});
landMap[r][c] = labal;
while(!queue.isEmpty()) {
int[] tmp = queue.poll();
cnt++;
for(int i = 0; i < 4; i++) {
int nr = tmp[0] + dr[i];
int nc = tmp[1] + dc[i];
if(nr < 0 || nc < 0 || nr >= N || nc >= M || landMap[nr][nc] != 1)
continue;
queue.offer(new int[] {nr, nc});
landMap[nr][nc] = labal;
}
}
map.put(labal++, cnt);
}
}