【 힘 단 추 】 200: 섬 수 | BFS 범위 우선 검색

제목 설명
'1' (육지) 과 '0' (물) 으로 구 성 된 2 차원 격자 를 드 리 겠 습 니 다. 격자 에 있 는 섬의 수 를 계산 해 보 세 요.
섬 은 항상 물 에 둘러싸 여 있 고 모든 섬 은 수평 방향 과 / 또는 수직 방향 으로 인접 한 육지 로 만 연결 되 어 있다.
그 밖 에 이 격자 의 네 변 이 모두 물 에 둘러싸 여 있다 고 가정 할 수 있다.
알고리즘 사고
섬 은 상하 좌우 로 땅 과 연결 되 지 않 는 다.
표준 BFS 는 배열 을 직접 옮 겨 다 니 며 원소 가 1 일 때 상하 좌우 로 확산 하기 시작 하고 1 을 만나면 확산 목록 을 추가 하고 확산 목록 이 비어 있 을 때 까지 값 을 0 으로 수정 합 니 다.
이렇게 전체 배열 을 옮 겨 다 니 는 과정 에서 만 나 는 1 의 수량 은 섬의 수량 이다.(상하 좌우 의 확산 방식 때문에 육 지 는 다른 섬 으로 확산 할 수 없다)

class Solution:
    def numIslands(self, grid) -> int:
        if not grid:return 0
        tp=[]
        diretion=[(0,1),(0,-1),(1,0),(-1,0)]
        res=0
        m,n=len(grid),len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='1':
                    res+=1
                    grid[i][j]='0'
                    tp.append((i,j))
                    while tp:
                        for _ in range(len(tp)):
                            x,y=tp.pop(0)
                            for k in diretion:
                                x_n,y_n=x+k[0],y+k[1]
                                if 0<=x_n<m and 0<=y_n<n and grid[x_n][y_n]=='1':
                                    grid[x_n][y_n]='0'
                                    tp.append((x_n,y_n))

        return res

실행 시: 84 ms, 모든 Python 3 제출 에서 72.64% 의 사용자 메모리 소모: 14.2 MB, 모든 Python 3 제출 에서 6.67% 의 사용 자 를 격파 하 였 습 니 다.