[백준_4963] 섬의 개수 python

사실 앞서 2시간 넘게 풀던 문제가 시간초과에 걸려,

오늘은 여기까지만 하자 하고 일보 후퇴하였다.

매우 쉽게 해결 가능한 문제,,

while True:
    
    # w, h 입력
    w, h = map(int, input().split())
    
    # 종료조건
    if w == 0 and h == 0:
        break
    
    # grid 입력
    grid = [
        list(map(int, input().split()))
        for _ in range(h)
    ]

    # 함수들
    # in_range(x, y):
    def in_range(x, y):
        return 0 <= x and x < h and 0 <= y and y < w

    # is_connected(x, y)
    def is_connected(x, y):
        # 범위 내에 있고, 방문한 적 없고, 섬이면 가능
        return in_range(x, y) and not visited[x][y] and grid[x][y]

    # bfs()
    def bfs():
        while q:
            x, y = q.popleft()
            dxs, dys = [-1,-1,-1,0,0,1,1,1],[-1,0,1,-1,1,-1,0,1]
            for dx, dy in zip(dxs, dys):
                # 주변 위치
                nx, ny = x + dx, y + dy
                # 이어져있다면,
                if is_connected(nx, ny):
                    # 방문 처리 해 주고,
                    visited[nx][ny] = 1
                    # 큐에 넣어주기
                    q.append((nx, ny))

    # 설계

    # visited 설계 및 초기화
    visited = [
        [0] * w
        for _ in range(h)
    ]

    # 섬의 개수
    island = 0

    # 큐 사용준비
    from collections import deque
    q = deque()

    # grid를 돌면서
    for i in range(h):
        for j in range(w):
            # 만약 섬을 발견하고, 발견한 적 없는 섬이면,
            if grid[i][j] and not visited[i][j]:
                # 섬의 개수에 추가해주고
                island += 1
                # 방문 처리 해 주고
                visited[i][j] = 1
                # 큐에 넣어주고
                q.append((i, j))
                # bfs() 돌려주기
                bfs()
    
    # 섬의 갯수 출력
    print(island)