PentaS

문제 접근
재귀 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형

class Solution {
    int answer;

    public int solution(int[] numbers, int target) {
        answer = 0;
        dfs(numbers, target, 0, '+', 0);
        dfs(numbers, target, 0, '-', 0);

        return answer;
    }

    public void dfs(int[] numbers, int target, int sum, char ch, int idx) {
        switch (ch) {
            case '+':
                sum += numbers[idx];
                break;
            case '-':
                sum -= numbers[idx];
                break;
        }

        if (idx == (numbers.length - 1)) {
            if (sum == target) {
                answer++;
            }
        } else {
            dfs(numbers, target, sum, '+', idx + 1);
            dfs(numbers, target, sum, '-', idx + 1);
        }
    }
}

재귀함수를 이용한 DFS 알고리즘으로 접근을 했다.

DFS를 이용해야겠다는 생각은 했지만 stack을 이용한 DFS로 처음에 접근했다.

약간의 힌트를 통해 재귀함수로 방향을 바꾸었으나, dfs 메소드 반환형을 int로 해야한다는 강박에 return 조건을 어떻게 설정해야하나 고민했었다.

결국 다른 분의 코드를 참고하여 반환형을 void로 바꾸고 idx값 비교와 sum 값 비교를 통해 문제를 해결할 수 있었다.


핵심

1. 재귀함수 반환형 void
2. idx값이 배열 끝에 도달했을 때, sum이 target과 같은지 비교