mingssssss

1. 문제

2. 코드

import java.util.*;

class Solution {
    
    static int[][] picture;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int check;
    static int cnt;
    static int m;
    static int n;
    
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        
        this.m = m;
        this.n = n;
        this.picture = picture;
           
        visited = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (picture[i][j] != 0 && visited[i][j] == false) {
                    cnt = 1;
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, dfs(i, j));
                    numberOfArea++;
                }
            }
        }

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    private static int dfs (int r, int c) {
        
        visited[r][c] = true;
        
        for (int i = 0; i < 4; i++) {
            
            int nx = r + dx[i];
            int ny = c + dy[i];
            
            if (nx < 0 || ny < 0 || nx >= m || ny >= n) {
                continue;
            }
            
            if (picture[nx][ny] != picture[r][c] || visited[nx][ny] == true) {                
                continue;
            }
            
            cnt++;
            dfs(nx, ny);
        }
        
        return cnt;
    }
}

3. 리뷰

전에 bfs로 풀어봤지만, dfs 연습겸 다시 한번 풀어봤다.

영역이 몇 군데인지와 각 영역의 크기를 return 하는 문제이다.

입력 받고 2차원 배열로 순회하면서 해당 좌푯값이 0이 아니고 방문하지 않았다면

dfs 함수를 돌렸다.

들어오자마자 방문체크 해주고, 갈 수 있는 범위이면서 다음 탐색할 좌푯값이

현재 좌푯값과 같고 방문하지 않았다면 cnt++를 해주고 dfs를 돌렸다.

dfs를 돌려서 나온 값과 maxSizeOfOneArea를 Math.max를 통해 최신화 하고,

dfs를 한 번 들어왔다는 것은 영역의 개수가 증가한 것이므로 numberOfArea를 + 1 해줬다.

나온 값을 answer 배열에 넣고 return했다.

저번에 bfs로 풀었을 때는 뭔가 오류가 많이 났는데, dfs로 풀 때는 오류가 없었다.

bfs보다 코드도 훨씬 깔끔하고 구현도 쉬워서 앞으로 비슷한 문제가 나오면

dfs로 풀어야겠다.