[Hackerrank] [Hard] DFS: Connected Cell in a Grid

https://www.hackerrank.com/challenges/ctci-connected-cell-in-a-grid/problem

DFS: Connected Cell in a Grid | HackerRank

풀이

• 0과 1로 구성된 grid가 주어지면, 1을 기준으로 한 영역의 최댓값을 구하는 문제.
  • 8가지 방향에 1이 있으면 같은 영역이라 가정.(왼쪽 대각선 위부터 시계방향)
• visited를 확인하기 위한 matrix 만들고, 방향 정보 리스트 만들고, stack을 사용해 dfs 구현하면 됨.

def maxRegion(grid):
    n = len(grid)
    m = len(grid[0])
    ans = []
    visited = [[0 for _ in range(m)] for _ in range(n)]
    # 다음 좌표 방향을 저장한 리스트.
    # 왼쪽 대각선 위로부터해서 시계방향으로 순회.
    di = [-1, -1, -1, 0, 1, 1, 1, 0 ]
    dj = [-1, 0, 1, 1, 1, 0, -1, 1 ]
    for i in range(n):
        for j in range(m):
            # grid 값이 1이고, 아직 방문하지 않은 위치임.
            if grid[i][j] == 1 and visited[i][j] == 0:
                stack = [(i, j)]
                visited[i][j] = 1
                cnt = 1
                while stack:
                    ii, jj = stack.pop()
                    for dir in range(8):
                        next_i = ii + di[dir]
                        next_j = jj + dj[dir]
                        
                        if 0 <= next_i < n and 0 <= next_j < m and \
                        grid[next_i][next_j] and visited[next_i][next_j] == 0:
                            stack.append((next_i, next_j))
                            # stack에 추가할 때 visited를 1로 바꿔줘야 나중에 방문한 곳을 stack에 중복해서 넣지 않음.
                            visited[next_i][next_j] = 1
                            cnt += 1
                ans.append(cnt)

    return max(ans)