Connected Cells in a Grid

사이트: HackerRank
난이도: 미디움
분류: Search

문제

어떤 행렬의 요소가 되는 값이 0과 1일 때, 1의 값을 가지는 셀이 연결된 영역의 최대 넓이를 구해라.

여기서 연결되어 있다고 하는 것은 해당 셀 주변으로 1칸씩 인접해 있다는 말이다. 즉, 값이 1인 셀(A) 주변에 1 값을 가지는 다른 셀(B)이 있다면 A와 B는 연결되어 있다고 할 수 있다.

1. 나의 풀이

이런 그리드 형식을 탐색하는 알고리즘이 나올 경우 거의 90퍼센트 이상으로 dfs, bfs 알고리즘을 적용하는 문제인 것 같다. javascript는 shift 연산이 더 오래 걸리므로 비교적 시간 소요가 덜 되는 push 연산을 할 수 있도록 dfs 알고리즘으로 구현하였다.

function dfs(matrix, i, j, map) {
  	// 가로 세로 길이
    const yn = matrix.length,
        xn = matrix[i].length;

  	// 역시나 방문 여부를 기록하는 변수를 설정해야 한다.
    const visited = Array.from(
        new Array(yn),
        () => new Array(xn).fill(false)
    );

  	// 인접한 모든 좌표 미리 선언
    const px = [1, 1, 1, 0, -1, -1, -1, 0],
        py = [1, 0, -1, -1, -1, 0, 1, 1];

  	// dfs 연산을 할 stack 생성
    const stack = [[j, i]];
    // 이미 본인도 '1' 값을 가지고 있기 때문에 미리 count 해둔다.
	let count = 1;
  	// 마찬가지로 현재 기준 셀 방문 활성화 해둔다.
    visited[i][j] = true;

    while (stack.length) {    
        const [x, y] = stack.pop();
        
        for (let i = 0; i < 8; i++) {
            const dx = x + px[i],
                dy = y + py[i];

            if (
              	// 인접한 셀의 값이 1이고 방문하지 않은 경우
                (0 <= dx && dx < xn) &&
                (0 <= dy && dy < yn) &&
                matrix[dy][dx] == 1 &&
                !visited[dy][dx]
            ) {
              	// count 증가
                count++;
              	// stack 추가
                stack.push([dx, dy]);
                visited[dy][dx] = true;

              	// 이후 루프에서 이미 확인된 셀을 다시 연산하지 않기 위한 맵을 기록한다.
                map.set(`${dy}${dx}`, true);
            }
        }
    }
    
    return count;
}

function connectedCell(matrix) {
    // Write your code here
    const map = new Map();
    let max = 0;
    
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[i].length; j++) {
          	// 이미 연산된 셀이 아니고 '1' 값을 가지는 셀이라면 dfs를 수행한다.
            if (!map.has(`${i}${j}`) && matrix[i][j] === 1) {
                const count = dfs(matrix, i, j, map);
                max = Math.max(count, max);
            }
        }
    }
    
    return max;
}

2. 다른사람의 풀이

바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.