Algorithm[Number Of Islands - LeetCode]

1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을때, 섬의 개수를 구하라.

(첫째 줄에는 맵의 열(col), 행(row)의 크기가 주어지고 둘째 줄부터 맵이 주어진다.)

입력
5 4
1 1 0 1 1
1 1 0 0 0
0 1 0 0 0
0 1 0 0 1
출력
3

✏️ 문제풀이 (dfs)

맵을 탐색하며 1을 만나면 인접한 1들을 모두 0으로 만들고, 섬의 개수를 하나 더한다.

def dfs(r, c):
    if r < 0 or r >= row or c < 0 or c >= col:
        return False
    
    if graph[r][c] == 0:
        return False
    
    if graph[r][c] == 1:
        graph[r][c] = 0
        dfs(r-1, c)
        dfs(r+1, c)
        dfs(r, c-1)
        dfs(r, c+1)
        return True

graph = []
count = 0
col, row = map(int, input().split())

for i in range(row):
    graph.append(list(map(int, input().split())))
    
for i in range(row):
    for j in range(col):
        if dfs(i, j) == True:
            count += 1

print(count)

Time Complexity: O(row * col)