문제 링크

문제 간단 해석

무난한 BFS, DFS 문제.

풀이 코드

import java.util.Stack;

class Solution {
    class Position {
        private int y;
        private int x;
        
        Position(int y, int x) {
            this.y = y;
            this.x = x;
        }
        
        public int getY() {
            return y;
        }
        
        public int getX() {
            return x;
        }
    }
    
    public int[] solution(int m, int n, int[][] picture) {
        int row = picture.length;
        int col = picture[0].length;
        boolean[][] check = new boolean[row][col];
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        int[] dy = {1, 0, -1, 0};
        int[] dx = {0, 1, 0, -1};
        Stack<Position> stack = new Stack<>();
        Position position;
        int y, x, r, c, count;
        
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (picture[i][j] != 0 && !check[i][j]) {
                    numberOfArea++;
                    count = 0;
                    check[i][j] = true;
                    stack.push(new Position(i, j));
                    
                    while (!stack.isEmpty()) {
                        position = stack.pop();
                        y = position.getY();
                        x = position.getX();
                        count++;
                        
                        for (int to = 0; to < 4; to++) {
                            r = y + dy[to];
                            c = x + dx[to];
                            
                            if (0 <= r && r < row && 0 <= c && c < col &&
                            picture[r][c] == picture[y][x] && !check[r][c]) {
                                check[r][c] = true;
                                stack.push(new Position(r, c));
                            }
                        }
                    }
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, count);
                }
            }
        }

        return new int[] {numberOfArea, maxSizeOfOneArea};
    }
}

해석

class Position {
    private int y;
    private int x;

    Position(int y, int x) {
        this.y = y;
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public int getX() {
        return x;
    }
}

위치를 기록할 클래스를 만들었다.
C++에서는 Pair로 했던 것 같은데, 자바는 만들어서 하는게 더 나은 듯 싶다.

int row = picture.length;
int col = picture[0].length;
boolean[][] check = new boolean[row][col];
int numberOfArea = 0;
int maxSizeOfOneArea = 0;
int[] dy = {1, 0, -1, 0};
int[] dx = {0, 1, 0, -1};
Stack<Position> stack = new Stack<>();
Position position;
int y, x, r, c, count;

사용할 녀석들을 많이 만들어뒀다.
row, col은 주어진 pircture의 크기이다.
check은 picture와 같은 크기의 2차원 배열인데, 해당하는 부분을 거쳤는지 거치지 않았는지 확인하는 용도이다. picture 값을 변형시켜도 되나, 원본은 건드리지 않는 게 여러모로 좋기에 따로 선언했다.
numberOfArea는 영역의 갯수, maxSizeOfOneArea는 한 영역의 최대 범위이다.
dy, dx는 상하좌우 네 방향 선언을 위함이다.
DFS를 사용할 예정이라 Stack을 선언했다. 재귀를 돌리지 않고도 DFS가 가능하다.
Position을 받아줄 객체를 따로 선언했다.
계속 사용될 y, x, r, c, count도 미리 선언. y, x, r, c는 해당 위치를, count는 영역의 넓이를 셀 것이다.

for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        if (picture[i][j] != 0 && !check[i][j]) {
            numberOfArea++;
            count = 0;
            check[i][j] = true;
            stack.push(new Position(i, j));
        	...
        }
        ...
    }
    ...
}

i, j를 돌리며 picture의 해당 위치값을 확인한다.
만약 picture 위치값이 0이 아니고(색칠이 되어있고), check 위치값이 false라면(처음으로 체크하는 거라면) 영역값을 1 늘리고 체크, 스택에 넣는다.

while (!stack.isEmpty()) {
    position = stack.pop();
    y = position.getY();
    x = position.getX();
    count++;

    for (int to = 0; to < 4; to++) {
        r = y + dy[to];
        c = x + dx[to];

        if (0 <= r && r < row && 0 <= c && c < col &&
            picture[r][c] == picture[y][x] && !check[r][c]) {
            check[r][c] = true;
            stack.push(new Position(r, c));
        }
    }
}
maxSizeOfOneArea = Math.max(maxSizeOfOneArea, count);

스택이 빌 때까지 계속 반복하여 돌린다.
스택의 최근값을 불러와 y와 x를 호출하고 count를 1 늘린다.
그 후 한 지점의 상하좌우를 보기 위해 to를 선언한다.

만약 해당 지점의 상, 하, 좌, 우가 picture 크기 안이면서 색이 같고(같은 영역) 지금까지 체크하지 않은 녀석이라면, 체크 후 stack에 넣어 같은 일을 반복하게끔 한다(해당 위치의 상하좌우를 또 확인하고, 또 체크하고, 또 넣고..).

만약 해당 영역의 모든 지점을 확인하여 stack에 더 이상 값이 추가되지 않아 최종적으로 stack이 비게 된다면, maxSizeOfOneArea와 count를 비교하여 최댓값을 들고 있게끔 한다.

return new int[] {numberOfArea, maxSizeOfOneArea};

마지막으로 영역의 갯수와 가장 큰 넓이를 반환한다.