Connected Cells in a Grid

Problem Link
https://www.hackerrank.com/challenges/connected-cell-in-a-grid/problem?isFullScreen=true

✅ Problem Summary

주어진 행렬에서 수평(horizontally), 수직(vertically), 대각(diagonally)으로 이어진 구역(1로 표시) 중 가장 넓은 구역의 크기를 구하는 문제

---

🧮 Applied Theory & Algorithm

1. 깊이 우선 탐색(Depth-First Search)

그림출처:Wikipedia

---

📑 My Answer

• 모든 테스트 케이스 통과

def dfs(matrix, tempCnt, matsize, pos):
    matrix[pos[0]][pos[1]] = 0
    dx = [0, 0, 1, 1, 1, -1, -1, -1]
    dy = [1, -1, 0, 1, -1, 0, 1, -1]
    for i in range(8):
        ni, nj = pos[0] + dx[i], pos[1] + dy[i]
        if 0 <= ni < matsize[0] and 0 <= nj < matsize[1] and matrix[ni][nj] == 1:
            tempCnt = dfs(matrix, tempCnt + 1, matsize=matsize, pos=(ni, nj))
    return tempCnt

def connectedCell(n, m, matrix):
    maxCnt = 0
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 1:
                tempCnt = dfs(matrix, 1, matsize=(n, m), pos=(i, j))
                maxCnt = max(tempCnt, maxCnt)
    return maxCnt

📌 코드 구현 설명

• 여러 경우의 수가 아닌 특정 위치에서 하나의 구역을 찾는 문제이기 때문에 DFS를 적용
• 행렬을 탐색하면서 1을 만날 때 마다 DFS 알고리즘을 사용하여 구역의 크기를 계산함 (DFS 함수를 만들어 재귀의 형태로 구현)
• DFS 함수에서, 방문한 위치에는 0을 넣어 다시 방문하지 못하게 만듦
• DFS 함수를 통해 return된 값을 매 행렬 탐색마다 비교하여 최댓값을 계산

---

💼 Takeaway

• DFS 문제 유형에 대해 감을 잡을 수 있었다.

---