[백준-4963] 섬의 개수 - Python

 

 

문제 소개

 

 

 

 

사용한 알고리즘

 

 

DFS
모든 점에서 DFS를 시작하고 육지일 경우 연속된 육지는 탐색 할때마다 바다 처리를 해준다

 

 

 

Code 

 

import sys
import collections

#sys.stdin = open("input.txt", "r")

input = sys.stdin.readline
sys.setrecursionlimit(10000)

def DFS(x0, y0):
    Arr[x0][y0] = 0
    mx = [0, 0, 1, -1, 1, -1, 1, -1]
    my = [1, -1, 0, 0, 1, -1, -1, 1]

    for k in range(8):
        newx = mx[k] + x0
        newy = my[k] + y0

        if 0 <= newx < N and 0 <= newy < M and Arr[newx][newy] == 1:
            DFS(newx, newy)


result_list = []

while 1:
    M, N = map(int, input().split(" "))
    if M == 0 and N == 0:
        break
    Arr = []
    for i in range(N):
        Arr.append(list(map(int,input().split(" "))))

    LandNum = 0
    for ix in range(N):
        for iy in range(M):
            if Arr[ix][iy] == 1:
                LandNum += 1
                DFS(ix, iy)
    result_list.append(LandNum)



for x in range(len(result_list)):
    print(result_list[x])

 

 

 

※ end