[백준] 4963 섬의 개수 / 파이썬

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

 

입력

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0​

출력

0
1
1
3
1
9​

 

코드 풀이

전형적인 DFS 문제이다.

1012 유기농 배추와 비슷한 문제이고, 체크할 방향이 상하좌우 뿐만 아니라 대각선 체크가 추가되었다.

import sys
sys.setrecursionlimit(10**6)

def dfs(x,y):

    if x < 0 or x>=h or y < 0 or y >= w:
        return False

    if island[x][y] == 1:
        island[x][y] = 0

        # 상하좌우
        dfs(x, y - 1)
        dfs(x - 1, y)
        dfs(x, y + 1)
        dfs(x + 1, y)

        # 대각선
        dfs(x - 1, y - 1)
        dfs(x - 1, y + 1)
        dfs(x + 1, y + 1)
        dfs(x + 1, y - 1)
        return True

    return False

while True:
    w, h = map(int, sys.stdin.readline().split())
    island = []
    cnt = 0

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

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

    for i in range(h):
        for j in range(w):
            if dfs(i,j):
                cnt += 1

    print(cnt)