[리트코드 3619] 값의 합이 k로 나누어지는 섬 세기 — BFS로 연결 요소 합산

원제: Count Islands With Total Value Divisible by K

문제 요약

양의 정수로 표시된 칸을 땅으로 보고, 가로·세로로 연결된 땅의 묶음마다 값의 합을 구합니다. 그 합이 양의 정수 k로 나누어떨어지는 섬의 개수를 반환합니다.

조건과 입출력

grid는 m x n 행렬이며 1 <= m, n <= 1000, 1 <= m * n <= 10^5입니다. 각 grid[i][j]는 0 이상 10^6 이하이고, 1 <= k <= 10^6입니다. 0은 땅이 아니며, 섬은 양수인 칸만으로 이루어진 4방향 연결 요소입니다.

예제와 문제 자료

예제 1: Input: grid = [[0,2,1,0,0],[0,5,0,0,5],[0,0,1,0,0],[0,1,4,7,0],[0,2,0,0,8]], k = 5 / Output: 2. 네 섬 중 합이 5로 나누어지는 섬이 두 개입니다. 예제 2: Input: grid = [[3,0,3,0], [0,3,0,3], [3,0,3,0]], k = 3 / Output: 6. 양수 칸들이 서로 4방향으로 닿지 않아 섬이 여섯 개이고, 각 합 3은 k로 나누어집니다.

풀이 아이디어

각 양수 칸에서 아직 방문하지 않았다면 BFS를 시작해 그 칸이 속한 섬 전체를 한 번에 탐색합니다. 큐에서 꺼낸 칸의 값을 total에 더하고, 탐색이 끝난 뒤 total % k == 0이면 answer를 증가시킵니다. BFS는 4방향으로 연결된 양수 칸을 모두 방문하므로 total은 정확히 한 섬의 합입니다. 방문 표시를 큐에 넣을 때 하므로 같은 칸이 여러 경로에서 중복으로 큐에 들어가지 않습니다. 바깥 반복문은 모든 칸을 확인하므로 어떤 섬도 빠뜨리지 않습니다.

코드의 핵심

코드에서는 n = len(grid)가 행 개수이고 m = len(grid[0])가 열 개수입니다. 따라서 visited도 n행 m열로 만들며, 좌표 범위는 0 <= sx < n, 0 <= sy < m으로 검사합니다. 이름과 달리 n을 열 개수로 쓰지 않는 점에 주의합니다.

BFS(i,j)는 시작 칸을 큐에 넣고 즉시 visited[i][j] = True로 표시합니다. 매 반복에서 큐의 맨 앞을 꺼내 grid[x][y]를 total에 더하고, directions의 네 이웃 중 범위 안에 있고 grid[sx][sy] > 0이며 미방문인 칸만 큐에 추가합니다. 이 조건은 물(0), 격자 밖, 이미 처리한 땅을 걸러냅니다.

코드 추적: 예제 2에서는 각 양수 칸이 대각선으로만 인접하고, 대각선 이동은 허용되지 않습니다. 따라서 BFS가 시작되는 섬은 총 여섯 개이며 각 섬의 total은 3입니다. 매번 total % k == 0이 참이 되어 answer가 6이 되고, 반환값은 6입니다.

전체 탐색은 행 우선으로 진행합니다. 바깥 반복문에서 grid[i][j] > 0 and not visited[i][j]일 때만 BFS를 호출하므로 이미 다른 BFS에서 방문한 섬은 다시 세지 않습니다.

제출 코드

from collections import deque

class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        n = len(grid)
        m = len(grid[0])

        visited = [[False]*m for i in range(n)]
        answer = 0
        directions = [(1,0),(-1,0),(0,1),(0,-1)]

        def BFS(i,j):
            nonlocal answer
            queue = deque()
            queue.append((i,j))
            visited[i][j] = True

            total = 0
            while queue:
                x,y = queue.popleft()
                total += grid[x][y]
                for dx,dy in directions:
                    sx,sy = x+dx,y+dy
                    if 0<=sx<n and 0<=sy<m and grid[sx][sy] > 0 and not visited[sx][sy]:
                        queue.append((sx,sy))
                        visited[sx][sy] = True

            if total % k == 0:
                answer += 1

        for i in range(n):
            for j in range(m):
                if grid[i][j] > 0 and not visited[i][j]:
                    BFS(i,j)

        return answer

복잡도

N = m * n이라 두면 각 칸은 visited 처리 후 한 번만 큐에 들어가고, 각 칸에서 네 방향을 확인하므로 시간 복잡도는 O(N)입니다. visited는 O(N) 보조 공간이고, 한 BFS의 큐도 최악에는 O(N)입니다. 반환값 answer 자체는 섬 개수만 저장하므로 O(1) 추가 공간입니다.

복습 포인트

양수 여부가 땅의 판정 기준이며, 합산 대상도 섬에 속한 양수 칸뿐입니다. 연결은 상하좌우만 인정하므로 대각선으로 닿는 칸은 같은 섬이 아닙니다. 코드에서 len(grid[0])을 사용하므로 입력 행렬에 최소 한 행이 있어야 합니다.

출처

문제 원문