[백준] 4963번 섬의개수, 플러드필 예제 (python3)

문제설명

https://www.acmicpc.net/problem/4963

나의 풀이

이 문제도 플러드필 알고리즘을 활용한 예제이다.
이차원배열의 모든 원소에 대하여 검증하여 좌,우,아래,위뿐 아니라 대각선 방향까지 탐색하여 연결요소의 개수를 구하는 문제이다.

import sys
sys.setrecursionlimit(100000)

def dfs(x, y):
    if x < 0 or y < 0 or x >= h or y >= w or visited[x][y] == 1 or matrix[x][y] == 0:
        return

    visited[x][y] = 1
    dfs(x-1, y)
    dfs(x-1, y+1)
    dfs(x, y+1)
    dfs(x+1, y+1)
    dfs(x+1, y)
    dfs(x+1, y-1)
    dfs(x, y-1)
    dfs(x-1, y-1)

while(1):
    w, h = map(int,sys.stdin.readline().split())

    if w == 0 and h == 0:
        break
    else:

        matrix = list()
        visited = [[0]*w for _ in range(h)]

        for _ in range(h):
            input_maps = list(map(int,sys.stdin.readline().split()))
            matrix.append(input_maps)

        cnt = 0
        for i in range(h):
            for j in range(w):
                if visited[i][j] == 0 and matrix[i][j] == 1:
                    dfs(i, j)
                    cnt += 1

        print(cnt)