static int[] dx = {0, 0, 1, -1};

static int[] dy = {1, -1, 0, 0};

static class Coord {

int x, y;

int groupArea;

Coord (int x, int y, int groupArea) {

this.x = x;

this.y = y;

this.groupArea = groupArea;

}

}

static int N, M;

static int[][] coordGroupId; // 각 좌표에 해당하는 그룹 id 배열

static Map<Integer, Integer> coordMap; // coordMap: 그룹 id - 그룹 area 가 매핑된 HashMap

static boolean[][] visited;

static ArrayDeque<Coord> queue;

public int solution(int[][] land) {

N = land.length;

M = land[0].length;

coordGroupId = new int[N][M];

coordMap = new HashMap<>();

visited = new boolean[N][M];

int groupId = 0;

for (int row = 0; row < N; row++) {

for (int col = 0; col < M; col++) {

if (land[row][col] == 1 && !visited[row][col]) {

visited[row][col] = true;

bfs(land, row, col, groupId);

}

groupId++;

}

}

return calculate(land);

}

public void bfs(int[][] land, int row, int col, int groupId) {

int groupArea = 1;

queue = new ArrayDeque<>();

queue.addLast(new Coord(row, col, groupArea));

while(!queue.isEmpty()) {

Coord c = queue.pollFirst();

int x = c.x;

int y = c.y;

coordGroupId[x][y] = groupId;

for (int i = 0; i < 4; i++){

int newX = x + dx[i];

int newY = y + dy[i];

if (newX < 0 || newX >= N || newY < 0 || newY >= M) continue;

if (land[newX][newY] == 0) continue;

if (visited[newX][newY]) continue;

visited[newX][newY] = true;

groupArea++;

queue.addLast(new Coord(newX, newY, groupArea));

}

}

coordMap.put(groupId, groupArea);

}

public int calculate(int[][] land) {

int maxArea = 0;

for (int col = 0; col < M; col++) {

int area = 0;

Set<Integer> groupSets = new HashSet<>();

for (int row = 0; row < N; row++) {

if (land[row][col] == 1) {

if (!groupSets.contains(coordGroupId[row][col])) {

groupSets.add(coordGroupId[row][col]);

area += coordMap.get(coordGroupId[row][col]);

}

}

}

maxArea = Math.max(maxArea, area);

}

return maxArea;

}

public static void main(String[] args) {

Solution250136 s = new Solution250136();

System.out.println(s.solution(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}

}));

System.out.println(s.solution(new int[][] {

{1, 0, 1, 0, 1, 1}, {1, 0, 1, 0, 0, 0}, {1, 0, 1, 0, 0, 1}, {1, 0, 0, 1, 0, 0}, {1, 0, 0, 1, 0, 1}, {1, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 1}

}));

}

}