[2017 카카오코드 예선] 카카오프렌즈 컬러링북 (JAVA)

문제

---

풀이

DFS로 접근했다가 답이 안 나와서 검색했더니, BFS로 푸는 게 더 효율적인 문제라는 것을 알게 되었다..! 그리고 Queue보다는 Stack을 사용하는 것이 더 효율적인 방법이라고 한다.

1. 모든 좌표를 차례로 탐색하며 조건에 맞는지 체크한다.
   • 아직 방문하지 않은 0이 아닌 좌표인 경우, 해당 영역 탐색을 시작한다.
   • stack에 상하좌우 좌표를 추가로 쌓아가며 해당 영역을 모두 탐색한다. 이 때 같은 색의 좌표만 stack에 넣을 수 있도록 조건을 추가로 체크한다.
   • 영역의 크기가 최댓값인 경우 maxSizeOfOneArea를 갱신한다.

---

코드

import java.util.*;

class Solution {
    
    private static final int NULL = 0;
    private static final int[] dx = {1, -1, 0, 0};
    private static final int[] dy = {0, 0, 1, -1};

    private int[][] pic;
    private int width, height;
    private boolean[][] visited;
    private int numberOfArea;
    private int maxSizeOfOneArea;

    public int[] solution(int m, int n, int[][] picture) {
        this.pic = picture;
        this.height = m;
        this.width = n;
        this.visited = new boolean[height][width];
        for (boolean[] each : visited) Arrays.fill(each, false);
        bfs();
        return new int[]{this.numberOfArea, this.maxSizeOfOneArea};
    }

    private void bfs() {
        Stack<Point> stack = new Stack<>();
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                int count = 0;
                if (!visited[y][x] && pic[y][x] != NULL) {
                    visited[y][x] = true;
                    stack.push(new Point(y, x));
                    count++;
                    numberOfArea++;
                }

                while (!stack.isEmpty()) {
                    Point current = stack.pop();
                    for (int i = 0; i < dy.length; i++) {
                        Point next = new Point(current.y + dy[i], current.x + dx[i]);
                        if (next.isPointInBound(width, height) && !visited[next.y][next.x] && pic[next.y][next.x] == pic[current.y][current.x]) {
                            visited[next.y][next.x] = true;
                            stack.push(next);
                            count++;
                        }
                    }
                }
                maxSizeOfOneArea = Math.max(count, maxSizeOfOneArea);
            }
        }
    }
}

class Point {

    int y;
    int x;

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

    public boolean isPointInBound(int width, int height) {
        return isXInBound(width) && isYInBound(height);
    }

    private boolean isXInBound(int width) {
        return this.x >= 0 && this.x < width;
    }

    private boolean isYInBound(int height) {
        return this.y >= 0 && this.y < height;
    }
}

---

참고

[프로그래머스][JAVA] 카카오프렌즈 컬러링북