문제 링크: https://programmers.co.kr/learn/courses/30/lessons/1829

문제 접근

재귀 DFS로 문제를 접근함

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

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

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

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

• 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형