Connected Cells in a Grid

문제: Connected Cells in a Grid

난이도: Medium

 

문제 설명

 가로n, 세로m의 그리드가 있고, 그리드 각각의 칸에는 0 또는 1의 값이 있다. 1이 인접해있는 부분을 region이라고 하면, 그리드에서 가장 큰 region의 크기를 구하여라.

 예를 들어 그리드가 다음과 같이 주어졌을 경우

1 1 0 0

0 1 1 0

0 0 1 0

1 0 0 0

가장 큰 region의 크기는 5이다.

 

문제 해결

소스 코드

public static int r;
    public static int rowMax;
    public static int colMax;
    public static List<Integer> size;
 
	static int connectedCell(int[][] matrix) {
        rowMax = matrix.length;
        colMax = matrix[0].length;
        r = 1;
        size = new ArrayList<Integer>();

        int result = 0;
 
        for(int i = 0; i < rowMax; i++) {
            for(int j = 0; j < colMax; j++) {
                if(matrix[i][j]==1) {
                    r++;
                    size.add(0);
                    dfs(matrix, i, j);
                }
            }
        }
        
        for(int i = 0; i < size.size(); i++) {
            if(size.get(i)>result) {
                result = size.get(i);
            }
        }
        return result;
    }

 

    static void dfs(int[][] m, int row, int col) {
        m[row][col] = r;
        size.set(r-2, size.get(r-2)+1);

        if(row-1>=0 && m[row-1][col] == 1) {
            dfs(m, row-1, col);
        }
        if(row-1>=0 && col+1<colMax && m[row-1][col+1] == 1) {
            dfs(m, row-1, col+1);
        }
        if(col+1<colMax && m[row][col+1] == 1) {
            dfs(m, row, col+1);
        }
        if(row+1<rowMax && col+1<colMax && m[row+1][col+1] == 1) {
            dfs(m, row+1, col+1);
        }
        if(row+1<rowMax && m[row+1][col] == 1) {
            dfs(m, row+1, col);
        }
        if(row+1<rowMax && col-1>=0 && m[row+1][col-1] == 1) {
            dfs(m, row+1, col-1);
        }
        if(col-1>=0 && m[row][col-1] == 1) {
            dfs(m, row, col-1);
        }
        if(row-1>=0 && col-1>=0 && m[row-1][col-1] == 1) {
            dfs(m, row-1, col-1);
        }
    }

 

 

해설

 이 문제는 DFS(깊이우선탐색) 알고리즘을 사용하는 문제 중에 가장 전형적인 문제이다. 깊이우선탐색이란, 루트 노드 또는 임의의 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법으로, 모든 노드를 방문할 때 사용된다. DFS는 재귀 함수나 스택으로 구현된다.

 그리드에서 값이 1인 곳을 찾아서 DFS를 시작한다. DFS에서는 현재 위치의 값을 1이 아닌 값으로 바꿔 중복 탐색하지 않게 하고, 현재 위치에서 주변 8방향을 탐색하여 1인 값이 있으면 DFS를 재귀 호출하여 탐색을 계속하고, 없으면 끝낸다.

 하나의 region을 탐색할 때마다 그 region의 크기를 저장해두고, 탐색이 끝나면 가장 큰 값을 출력한다.