[2017 카카오코드]카카오프렌즈 컬러링북

📍 문제 설명

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

코딩테스트 연습 - 카카오프렌즈 컬러링북

 

💡 접근

BFS에서 각 영역의 갯수와 영역의 크기를 구하는 문제였다.

 

 

👩‍💻 코드

import java.util.*;

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

    public int[] solution(int m, int n, int[][] picture) {
        int maxSizeOfOneArea = 0;
        int numberOfArea = 0;

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

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                //그림 상하좌우 확인하여 영역, 넓이구하기
                if(picture[i][j] != 0 && !visited[i][j]) {
                    int size = BFS(i, j, m, n, picture, visited);
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, size);
                    numberOfArea++;
                }
            }
        }

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

    private int BFS(int x, int y, int m, int n, int[][] picture, boolean[][] visited) {
        int size= 1;

        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(x, y));
        visited[x][y] = true;

        while(!q.isEmpty()) {
            Point cp = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = cp.x + dx[i];
                int ny = cp.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= m || ny >= n || visited[nx][ny]) continue;

                //현재 영역과 같은 영역이면 영역 수 증가시키고 방문처리
                if (picture[nx][ny] == picture[cp.x][cp.y]) {
                    visited[nx][ny] = true;
                    q.offer(new Point(nx, ny));
                    size++;
                }
            }
        }
        return size;
    }

    public static void main(String[] args) {
        Solution s = new Solution();

        int m = 6;
        int n = 4;
        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}};
        //int[][] picture = new int[][]{{1}};
        s.solution(m, n, picture);
    }

    private class Point {
        private int x;
        private int y;

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

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}