카카오프렌즈 컬러링북

본 풀이는 java 언어를 사용하였습니다.
문제 보러가기

풀이

어피치 그림 예제와 예제 입출력이 무슨 관련이 있는지 영 이해가 안가서 계속 보다가
입출력만 살펴보자 해서 배열을 나열하니 대충 무슨 말인지 이해가 갔다.

위 모양을 보면 숫자별로 인접해있는 영역이 4개 임을 알 수 있다. (0은 빈 영역이라 제외한다)
그리고 숫자별로 가장 많은 개수는 5개 이다. (왼쪽 상단 1영역)
그래서 답이 [4, 5] 가 나오는 것이다.

이제 코드로 풀어보자.

for (int i = 0; i < picture.length; i++) {
    for (int j = 0; j < picture[0].length; j++) {
        if (visit[i][j] || picture[i][j] == 0) {
            continue;
        }
        bfs(i, j, picture);
    }
}

배열을 순회하면서 bfs 를 돌리면서 인접한 동일 숫자를 조회하면 된다.
여기서 이미 방문한 경우와 빈 구역 (0) 은 제외한다.

private void bfs(int x, int y, int[][] picture) {
    Queue<Point> points = new LinkedList<>();
    points.add(new Point(x, y, picture[x][y]));
    visit[x][y] = true;
    int sizeOfOneArea = 1;
    ...
}

Queue 를 이용해서 bfs 를 계산하였다.
참고로 bfs 란 인접한 동일 숫자를 반복문을 돌면서 계속해서 체크하면서 탐색하는 기법이다.
반복문이 끝나면 인접한 숫자가 더이상 없다는 것으로 생각하면 된다.
편의상 Point 객체를 아래와 같이 만들어 주었다.

class Point {

    private final int x;
    private final int y;
    private final int color;

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

    public boolean isSameColor(int targetColor) {
        return color == targetColor;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getColor() {
        return color;
    }
}

위처럼 탐색 시작점을 Queue 에 넣어주고 반복문을 돌린다.

private void bfs(int x, int y, int[][] picture) {
    Queue<Point> points = new LinkedList<>();
    points.add(new Point(x, y, picture[x][y]));
    visit[x][y] = true;
    int sizeOfOneArea = 1;

    while (!points.isEmpty()) {
        Point point = points.poll();

        for (int i = 0; i < 4; i++) {
            int nextX = point.getX() + X_DIR[i];
            int nextY = point.getY() + Y_DIR[i];

            // 범위를 벗어났는가
            if (nextX < 0 || nextY < 0 || nextX >= picture.length || nextY >= picture[0].length) {
                continue;
            }

            // 이미 방문 했는가
            if (visit[nextX][nextY]) {
                continue;
            }

            // 같은 영역인가
            if (!point.isSameColor(picture[nextX][nextY])) {
                continue;
            }

            points.add(new Point(nextX, nextY, point.getColor()));
            visit[nextX][nextY] = true;
            sizeOfOneArea++;
        }
    }
    numberOfArea++;
    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, sizeOfOneArea);
}

탐색 영역으로 부터 인접한 영역 (상, 하, 좌, 우) 을 탐색해야 하므로 for 문 4번을 돌게 된다.
그 후 nextX, nextY 값이 유효한 값인지 체크 후 정상적인 값이라면 Queue 에 더해준다.
숫자별로 가장 많은 개수도 구해야 하므로 sizeOfOneArea 값도 더해준다.
while 문이 끝난다는 것은 인접해있는 숫자가 더이상 없음을 나타내므로 numberOfArea (숫자 영역)를 1 더해준다.
숫자별로 가장 많은 개수 를 구해야 하므로, maxSizeOfOneArea 값과 비교해서 더 큰 값을 넣어준다.
이렇게 한다면 숫자별로 인접해있는 영역과 숫자별로 가장 많은 개수를 쉽게 구할 수 있게된다.

코드

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    private static final int[] X_DIR = {0, 0, -1, 1};
    private static final int[] Y_DIR = {-1, 1, 0, 0};
    private boolean[][] visit;
    private int numberOfArea;
    private int maxSizeOfOneArea;

    public int[] solution(int m, int n, int[][] picture) {
        visit = new boolean[m][n];

        for (int i = 0; i < picture.length; i++) {
            for (int j = 0; j < picture[0].length; j++) {
                if (visit[i][j] || picture[i][j] == 0) {
                    continue;
                }
                bfs(i, j, picture);
            }
        }

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

    private void bfs(int x, int y, int[][] picture) {
        Queue<Point> points = new LinkedList<>();
        points.add(new Point(x, y, picture[x][y]));
        visit[x][y] = true;
        int sizeOfOneArea = 1;

        while (!points.isEmpty()) {
            Point point = points.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = point.getX() + X_DIR[i];
                int nextY = point.getY() + Y_DIR[i];

                // 범위를 벗어났는가
                if (nextX < 0 || nextY < 0 || nextX >= picture.length || nextY >= picture[0].length) {
                    continue;
                }

                // 이미 방문 했는가
                if (visit[nextX][nextY]) {
                    continue;
                }

                // 같은 영역인가
                if (!point.isSameColor(picture[nextX][nextY])) {
                    continue;
                }

                points.add(new Point(nextX, nextY, point.getColor()));
                visit[nextX][nextY] = true;
                sizeOfOneArea++;
            }
        }
        numberOfArea++;
        maxSizeOfOneArea = Math.max(maxSizeOfOneArea, sizeOfOneArea);
    }
}

class Point {

    private final int x;
    private final int y;
    private final int color;

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

    public boolean isSameColor(int targetColor) {
        return color == targetColor;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getColor() {
        return color;
    }
}

회고

어피치 그림이 예제 입출력이랑 무슨 상관인지 잘 이해가 안갔는데,
입출력만 보면 같은 영역만 계산하면 되니까 bfs 를 쓰면 되겠구나 바로 느낌이 와서 구현했더니 바로 통과되서 조금 어이없었다.. (어피치 그림은 도대체 뭐였을까.. / 심지어 제출 테스트도 1개만 있는...)
오랜만에 bfs 로 풀어봤는데 예전에 하도 많이 풀었다보니 몸이 반응해서 조금 놀람..