프로그래머스 - 카카오컬러링북

요구사항

카카오 프렌즈 친구들이 컬러링북을 만드는데 영역이 많을 수록 난이도를 뭐 어렵게? 뭐 하여튼 그런식으로해서 영역을 구해야 된다고한다. (=> 전형적인 BFS 문제 )
그래서 영역중 제일 큰 영역의 크기와, 컬러링 북 내에 몇개의 영역이 있는지를 알려달라고 한다.

키워드

BFS 그리고 맵을 순회해야 하는 문제의 키워드는

        static boolean[][] visit;
        static int[] xMap = {-1,1,0,0};
        static int[] yMap = {0,0,1,-1};

위의 세가지가 핵심이다. visit 는 해당 Node 를 방문했는지를 알려주며, dx / dy 는 (상, 하, 좌, 우) 로 움직일 수 있게 해주는 좌표이다.
그래서 우리의 목표는 BFS 에 넣은 값들을 기반으로 상하좌우로 움직이면서 방문했으면 true 표시를 하고, 같은 영역인지 탐색하는 것이 목적이다.

해당 코드는 아래와 같다.

package Programmers;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class 카카오컬러링북 {

    public static void main(String[] args) {
        Solution solution = new Solution();
        final int[] solution1 = solution.solution(6, 4, 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}});
        System.out.println(Arrays.toString(solution1));
    }

    static class Solution {
        static boolean[][] visit;
        static int[] xMap = {-1,1,0,0};
        static int[] yMap = {0,0,1,-1};

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

            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(visit[i][j] || picture[i][j] == 0){
                        continue;
                    }
                    answer[1] = Math.max(answer[1], bfs(picture, i, j));
                    answer[0]++;
                }
            }
            return answer;
        }

        int bfs(int[][] picture, int x, int y){
            Queue<int[]> queue = new LinkedList<>();
            int area = 1, dx, dy;
            visit[x][y] = true;
            queue.offer(new int[]{x,y});

            while (!queue.isEmpty()){
                int[] poll = queue.poll();

                for(int i = 0; i < 4; i++){
                    dx = poll[0] + xMap[i];
                    dy = poll[1] + yMap[i];

                    if(dx >= 0 && dy >= 0 && dx < picture.length && dy < picture[0].length){
                        if(!visit[dx][dy] && picture[dx][dy] != 0 && picture[poll[0]][poll[1]] == picture[dx][dy]){
                            visit[dx][dy] = true;
                            queue.offer(new int[]{dx, dy});
                            area++;
                        }
                    }
                }
            }
            return area;
        }
    }
}

BFS

• BFS 는 노드를 하나하나씩 탐색하는 것으로 해당 문제를 풀때 DFS 보다 빠르다. 그래서 우리는 X | Y 로 탐색하면서 계속해서 영역을 찾아나가고 같지 않다면 area 를 추가하지 않는다. 해당 탐색이 끝나면 area를 리턴해준다. 그니까 같은 숫자일때 계속해서 도는것이다. BFS 는 보통 스택을 이용한다. 해당 BFS / DFS 개념을 정확히 잡으려면 프로그래머스 보다는 백준 알고리즘 단계별 풀이에서 BFS 와 DFS 를 이해갈때까지 풀어보는게 좋은듯 하다. 아무래도 프로그래머스는 개념을 잡기에는 좋은 싸이트는 아니라고 생각한다.

글을 쓰게 된 이유

알고리즘은 쓸것도 없고, 생각정리 정도인것 같아서 어지간해서 잘 안쓰려고 하는데.. 최근 계속푸는데도 이런 쉬운 문제에서 발목을 잡힐 줄은 몰랐다. 진짜 시간소모를 많이 하게되서 정리할 겸 쓰게 됬다.
토요일 코테인데 큰일났다~~! 이런 문제에 발목잡히면 답도없는데