bj섬의개수

DFS, BFS 둘다 풀 수 있는 문제

이미 방문한 곳은 훼손을 시켜서 다시 방문하지 않도록 만들어주면 되는 문제였음. 한 가지 다른 점은 대각선도 고려해줘야 한다는 것!
방문한 곳의 훼손은 data 값을 하나씩 더해서 1이 아닌 상태로 만들어 줬음!!

import sys


def dfs(graph, start):
    stack = [start]
    dx = [1,-1,0,0,1,1,-1,-1]
    dy = [0,0,1,-1,1,-1,1,-1]
    while stack:
        x, y = stack.pop()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<m and 0<=ny<n and graph[nx][ny] == 1:
                stack.append((nx,ny))
                graph[nx][ny] = graph[x][y] + 1


while True:
    n,m = map(int, input().split())
    if n == 0 and m == 0:
        break
    card = []
    for _ in range(m):
        card.append(list(map(int, sys.stdin.readline().split())))
    cnt = 0
    for i in range(m):
        for j in range(n):
            if card[i][j] == 1:
                cnt += 1
                dfs(card, (i,j))

    print(cnt)