문제

https://programmers.co.kr/learn/courses/30/lessons/1829

코드

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
public int[] solution(int m, int n, int[][] picture) {
    int numberOfArea = 0;
    int maxSizeOfOneArea = 0;

    boolean[][] isPassedArea = new boolean[m][n];

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {

            if (picture[i][j] == 0 || isPassedArea[i][j]) {
                continue;
            }

            int areaRange = breadthFirstSearch(i, j, picture, isPassedArea);
            maxSizeOfOneArea = (maxSizeOfOneArea < areaRange) ? areaRange : maxSizeOfOneArea;
            ++numberOfArea;
        }
    }

    int[] answer = new int[2];
    answer[0] = numberOfArea;
    answer[1] = maxSizeOfOneArea;

    return answer;
}

private int breadthFirstSearch(int x, int y, int[][] picture, boolean[][] isPassedArea) {
    final int[] xAround = new int[]{1, -1, 0, 0};
    final int[] yAround = new int[]{0, 0, 1, -1};

    int areaRange = 1;

    Queue<Position> queue = new LinkedList<Position>();

    setPassedArea(isPassedArea, queue, x, y);

    while (!queue.isEmpty()) {
        Position currentPosition = queue.poll();

        for (int i = 0; i < xAround.length; i++) {
            int moveX = xAround[i] + currentPosition.x;
            int moveY = yAround[i] + currentPosition.y;

            if (!isSameAreaValidation(moveX, moveY, picture, isPassedArea, currentPosition)) {
                continue;
            }

            setPassedArea(isPassedArea, queue, moveX, moveY);
            ++areaRange;
        }
    }

    return areaRange;
}

private boolean isSameAreaValidation(int moveX, int moveY, int[][] picture, boolean[][] isPassedArea, Position currentPosition) {
    if (isOutOfPicture(moveX, moveY, picture)) {
        return false;
    }

    if (picture[moveX][moveY] == 0) {
        return false;
    }

    if (isPassedArea[moveX][moveY]) {
        return false;
    }

    if (picture[currentPosition.x][currentPosition.y] != picture[moveX][moveY]) {
        return false;
    }

    return true;
}

private boolean isOutOfPicture(int moveX, int moveY, int[][] picture) {
    if (moveX < 0 || moveY < 0) {
        return true;
    }

    if (picture.length <= moveX || picture[0].length <= moveY) {
        return true;
    }

    return false;
}

private void setPassedArea(boolean[][] isPassedArea, Queue<Position> queue, int x, int y) {
    isPassedArea[x][y] = true;
    queue.offer(new Position(x, y));
}

class Position {
    private int x = 0;
    private int y = 0;

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

흐름

  1. 이미 지나온 배열인지 확인하기 위해 picture array와 똑같은 크기의 boolean array를 만듦
  2. 2차원 배열 크기만큼 돌면서 picture[i][j] value가 0이거나 이미 지나온 길이면 찾아갈 필요가 없으므로 continute 해서 길을 찾지 않음
  3. 아니면 좌표 x,y를 저장할 class를 담는 Queue를 생성함
  4. queue에 현재 좌표를 저장하고 boolean array[x][y]를 true로 할당
  5. queue에 있는 값을 하나씩 꺼내면서 queue가 전부 비워질 때까지 반복
  6. queue에서 꺼낸 현재 좌표에서 상하 좌우를 비교해서 같은지 판단해야 하므로 현재 좌표에서 x -1 , +1, y +1, -1 씩 돌아가면서 판단할 좌표를 구함
  7. 구한 좌표가 validation을 통과하면 4번과 마찬가지로 좌표를 queue에 저장하고 true로 변경
    1. 구한 좌표 x, y가 array 범위를 넘어가진 않는 지
    2. 구한 좌표의 value가 0이 아닌 값 인지
    3. 구한 좌표가 이미 지나간 길이 아닌지
    4. 구한 좌표의 value가 현재 좌표의 value와 같은 지
    5. 위 4가지를 모두 통과해야 validation 통과
  8. 현재 영역의 크기를 증가시킴
  9. queue가 전부 비워지면 영역의 크기를 return해서 이전에 구한 영역의 크기와 비교해서 큰 값을 저장
  10. 영역 개수를 증가시킴
  11. 끝

결과

결과

테스트 케이스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int[][] picture = new int[][] {{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}};
assertArrayEquals(new int[] {4 , 5}, test.solution(6, 4, picture));

int[][] picture1 = new int[][] {{0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}};
assertArrayEquals(new int[] {0 , 0}, test.solution(5, 5, picture1));

int[][] picture2 = new int[][] {{1, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 1}};
assertArrayEquals(new int[] {3 , 1}, test.solution(5, 5, picture2));

int[][] picture3 = new int[][] {{1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}};
assertArrayEquals(new int[] {1 , 25}, test.solution(5, 5, picture3));

int[][] picture4 = new int[][] {{1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 100, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}};
assertArrayEquals(new int[] {2 , 24}, test.solution(5, 5, picture4));

int[][] picture5 = new int[][] {{1, 1, 1, 0}, {1, 1, 1, 0}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}};
assertArrayEquals(new int[] {2 , 6}, test.solution(6, 4, picture5));

int[][] picture6 = new int[][] {{0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0}, {0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0}, {0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 0}, {0, 1, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 0}, {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0}, {0, 1, 3, 3, 3, 1, 1, 1, 1, 1, 1, 3, 3, 3, 1, 0}, {0, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 0}, {0, 0, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 0}, {0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0}};
assertArrayEquals(new int[] {12 , 120}, test.solution(13, 16, picture6));

참고 사이트