카카오프렌즈 컬러링북 (DFS, Java, 프로그래머스)

BFS와 기본적인 흐름은 거의 비슷하지만

BFS는 인접한 노드를 반복하며 큐에 쌓고 큐를 소모할 때까지 iteration을 반복하며 재귀적으로 호출하지 않고

DFS는 자기 자신을 재귀적으로 호출하며 콜스택에 쌓는 방식으로 구현한다.

 

DFS와 BFS에서 가장 중요한 것은 언제 어떤 조건으로 빠져나가는지를 결정하는 것이고 전체적인 흐름은 거의 비슷한 양상을 보이는 것같다.

 

해당 문제의 경우
static int numberOfArea;
static int maxSizeOfOneArea; 
와 같이 전역 변수로 꺼내는 경우 메인 메서드 내에서 다시 한번 초기화를 해야한다. 
프로그래머스 사이트 자체에 버그가 있다고 한다.

class Solution {
    static int numberOfArea;
    static int maxSizeOfOneArea;
    static int[][] D = {{1,0},{-1,0},{0,1},{0,-1}};
    static int temp = 0;
    
    public static void dfs(int row, int col, int[][] picture, boolean[][] visited) {
        if (visited[row][col]) return;
        
        visited[row][col] = true;
        temp++;
        
        for (int i = 0; i < 4; i++) {
            int newRow = row + D[i][0];
            int newCol = col + D[i][1];

            if (newRow < 0 || newRow >= picture.length || newCol < 0 || newCol >= picture[0].length) 
                continue;
            if (picture[row][col] == picture[newRow][newCol] && !visited[newRow][newCol]) 
                dfs(newRow, newCol, picture, visited);
        }
    }
    
    public int[] solution(int m, int n, int[][] picture) {
        numberOfArea =0;
        maxSizeOfOneArea=0;

        int[] answer = new int[2];
        boolean[][] visited = new boolean[m][n];
        
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (picture[row][col] != 0 && !visited[row][col]) {
                    numberOfArea++;
                    dfs(row, col, picture, visited);
                }
                if (temp > maxSizeOfOneArea) 
                    maxSizeOfOneArea = temp;
                temp = 0;
            }
        }
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;

        return answer;
    }
}