[Java] 카카오프렌즈 컬러링북

문제 접근
재귀 DFS로 문제를 접근함

1. 상하좌우에서 현재 체크 중인 값은 재귀 DFS 호출

2. 상하좌우에서 현재 체크 중인 값과 같지 않으면 해당 위치를 Stack에 저장함

3. 재귀 DFS가 끝나면 면적 체크해서 1 이상이면 면적 수 증가 & 면적 최대 크기 비교해서 갱신

3-1. 현재 체크 중인 값이 0이라면 3번 과정 진행X

4. Stack에 저장된 위치부터 1번 과정 진행

import java.util.*;

class Solution {
    static Stack<List<Integer>> anotherValueStack;
    static boolean[][] visit;
    static int visitCount;
    static int curAreaSize;
    static long[][] copiedPicture;

    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        int[] answer = new int[2];
        int mm = m;
        int nn = n;
        copiedPicture = new long[mm][nn];
        for (int i = 0; i < mm; i++) {
            for (int j = 0; j < nn; j++) {
                copiedPicture[i][j] = (long) picture[i][j];
            }
        }

        anotherValueStack = new Stack<>();

        visit = new boolean[mm][nn];
        for (int i = 0; i < mm; i++) {
            for (int j = 0; j < nn; j++) {
                visit[i][j] = false;
            }
        }
        visitCount = 0;
        curAreaSize = 0;

        int i = 0;
        int j = 0;
        long curValue = 0;
        List<Integer> initPos = new ArrayList<>();
        initPos.add(0);
        initPos.add(0);

        anotherValueStack.push(initPos);
        while (visitCount < mm * nn) {
            List<Integer> pos = anotherValueStack.pop();
            i = pos.get(0);
            j = pos.get(1);
            curValue = copiedPicture[i][j];
            curAreaSize = 0;
            dfs(i, j, mm, nn, curValue);

            //측정 영역 크기가 1이상이면 영역 수 증가 & 최대값 크기 갱신
            if (curAreaSize >= 1 && curValue != 0) {
                numberOfArea++; //영역 수 증가
                maxSizeOfOneArea = Math.max(maxSizeOfOneArea, curAreaSize);
            }
        }

        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }

    public void dfs(int i, int j, int m, int n, long curVal) {
        //이미 방문했으면 진행하지 않음
        if (!visit[i][j]) {
            visitCount++;
            visit[i][j] = true;
            curAreaSize++;

            //위
            if ((i - 1) >= 0) {
                if (copiedPicture[i - 1][j] == curVal) {
                    dfs(i - 1, j, m, n, curVal);
                } else {
                    List<Integer> pos = new ArrayList<>();
                    pos.add(i - 1);
                    pos.add(j);
                    anotherValueStack.push(pos);
                }
            }
            //아래
            if ((i + 1) < m) {
                if (copiedPicture[i + 1][j] == curVal) {
                    dfs(i + 1, j, m, n, curVal);
                } else {
                    List<Integer> pos = new ArrayList<>();
                    pos.add(i + 1);
                    pos.add(j);
                    anotherValueStack.push(pos);
                }
            }
            //왼쪽
            if ((j - 1) >= 0) {
                if (copiedPicture[i][j - 1] == curVal) {
                    dfs(i, j - 1, m, n, curVal);
                } else {
                    List<Integer> pos = new ArrayList<>();
                    pos.add(i);
                    pos.add(j - 1);
                    anotherValueStack.push(pos);
                }
            }
            //오른쪽
            if ((j + 1) < n) {
                if (copiedPicture[i][j + 1] == curVal) {
                    dfs(i, j + 1, m, n, curVal);
                } else {
                    List<Integer> pos = new ArrayList<>();
                    pos.add(i);
                    pos.add(j + 1);
                    anotherValueStack.push(pos);
                }
            }
        }
    }
}

"질문하기"를 보니 테스트 케이스를 모두 통과하더라도 채점만 하면 틀렸다는 분들이 많았습니다.

다음과 같은 조언을 반영해서 통과했습니다.

1. 모든 전역변수를 solution 메소드 내에서 초기화

2. picture배열을 복사해서 사용

3. 복사한 picture배열의 타입은 long형