프로그래머스 LV.2 카카오프렌즈 컬러링북

프로그래머스 LV.2 카카오프렌즈 컬러링북

1. 문제 링크

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

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

2. 문제 해결에 대한 아이디어

1. 이 문제는 이상하게 전역 변수를 solution 함수 내에서 초기화를 해야했다.
2. 해당 문제의 게시판을 확인해보면 solution 내에서 초기화하면 통과 된다는 글을 볼 수 있다.
3. 이 문제는 BFS를 사용했고 영역의 갯수를 세기 위해서 방문 배열인 visit에 영역의 번호를 저장했다.
4. 따라서, 코드 내에서 numberOfArea를 영역 번호로 사용하여 초기화를 1로 하고 답을 낼 때는 -1을 했다.
5. BFS를 수행하면 시작 위치를 중심으로 영역 번호가 매겨지게 되며, BFS가 끝난 후 영역 번호를 ++ 했다.

 

3. 코드

import java.util.ArrayDeque;
import java.util.Queue;

public class Solution {
    static class Pair {
        int y, x;

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

    }

    static int[][] visit;
    static int[] dirY; // 행 이동 방향
    static int[] dirX; // 열 이동 방향
    static int numberOfArea; // 영역 번호 (1번부터 시작)
    static int maxSizeOfOneArea; // 영역의 최대 크기

    public int[] solution(int m, int n, int[][] picture) {
        // 전역변수를 함수 내에서 초기화해줘야 통과됨 (왜인지는 모름)
        numberOfArea = 1;
        maxSizeOfOneArea = 0;
        dirY = new int[]{0, 0, 1, -1};
        dirX = new int[]{1, -1, 0, 0};
        visit = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 색이 칠해진 곳이면서, 어떤 영역에도 속하지 않는 경우
                if (picture[i][j] != 0 && visit[i][j] == 0) {
                    BFS(i, j, numberOfArea, m, n, picture);
                    numberOfArea++;
                }
            }
        }

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

        return answer;
    }

    public void BFS(int i, int j, int no, int m, int n, int[][] picture) {

        Queue<Pair> q = new ArrayDeque<>();
        q.add(new Pair(i, j));
        // 특정 번호로 영역 표시
        visit[i][j] = no;
        // 영역의 크기 카운트
        int cnt = 1;
        while (!q.isEmpty()) {
            Pair now = q.poll();

            for (int d = 0; d < 4; d++) {
                int yy = now.y + dirY[d];
                int xx = now.x + dirX[d];

                if (yy < 0 || xx < 0 || yy >= m || xx >= n 
                        || visit[yy][xx] != 0 || picture[yy][xx] != picture[i][j]) {
                    continue;
                }
                cnt++;
                visit[yy][xx] = no;
                q.add(new Pair(yy, xx));
            }
        }
        // 영역의 최대 크기 구하기
        maxSizeOfOneArea = Math.max(maxSizeOfOneArea, cnt);
    }
}

4. 채점 결과

5. 느낀 점

1. BFS를 사용하는 문제였다.
2. 영역을 각각 구분하기 위해 visit을 영역의 번호로 채우는 응용이 필요했다.
3. 다른 방법도 있을 것 같긴 하다.