백준 4963 - 섬의 개수

#백준 4963 (섬의 개수)           --> COUNT TOTAL # OF CONNECTED COMPONENTS FOR EACH GRAPH 

#백준 2667 (단지번호 붙이기) --> COUNT # OF HOUSE IN EACH CONNECTED COMPONENT IN 1 GRAPH 

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

 

4963번: 섬의 개수

#2A. DFS VERSION

dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

def DFS(x,y):
    global count
    if x < 0 or x >= h or y < 0 or y >= w:
        return False
    if graph[x][y] == 1:
        graph[x][y] = 0
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            DFS(nx,ny)
        return True # EACH ISOLATED COMPONENT OVER
    return False


while True:
    w,h = map(int,input().split())
    if w == 0 and h == 0:
        break
    graph = []
    count = 0
    for i in range(h):
        graph.append(list(map(int,input().split())))
    for i in range(h):
        for j in range(w):
            if DFS(i,j):
                count+=1
    print(count)

#2B. DFS VERSION

import sys
sys.setrecursionlimit(10000)
dx = [-1,-1,-1,1,1,1,0,0]
dy = [1,0,-1,1,0,-1,-1,1]
def DFS(x,y):
    global count
    VIS[x][y] = True
    if GRAPH[x][y] == 1:
        count += 1
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < M and 0 <= ny < N:
            if VIS[nx][ny] == False and GRAPH[nx][ny] == 1:
                DFS(nx,ny)

while True:
    N,M = map(int,input().split())
    if N == 0 and M == 0:
        break
    count = 0
    ANS = []
    GRAPH = [list(map(int,input().split())) for _ in range(M)]
    VIS = [[False]*N for _ in range(M)]
    for i in range(M):
        for j in range(N):
            if GRAPH[i][j] == 1 and VIS[i][j] == False:
                DFS(i,j)
                ANS.append(count)  # ONLY APPEND AFTER 상하좌우 FOR THIS ISOLATED COMPONENT IS OVER
                count = 0  # ISOLATED COMPONENT OVER, NESTED FOR LOOP ALL N x N
    print(len(ANS))