Number Of Island

https://leetcode.com/problems/number-of-islands/description/

그래프 이해도를 높이기 위한 인강을 시청중 제공해준 문제

문제이해

직관적인 문제라서 크게 이해를 도울것은 없는 것 같다 0은 물 1은 섬이며 1로 이루어진 땅 덩어리가 몇개인지 해결하는 그래프 문제이다

문제 포인트

그래프 문제이며 bfs를 활용하여 풀었는데 그래프쪽에선 가장 기초적인 문제라고 한다
땅 덩어리 시작 포인트를 주고 주변 땅을 모두 구해서 섬에다 +=1 을 해주면 된다

제출 코드

from collections import deque

def number_of_island(grid):
    island_number = 0
    x_len = len(grid[0])
    y_len = len(grid)
    print(x_len)
    print(y_len)
    visited = [[False] * x_len for _ in range(y_len)]

    def bfs(x, y):
        visited[x][y] = True
        queue = deque()
        queue.append((x, y))
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]

        while queue:
            cur_x, cur_y = queue.popleft()
            for i in range(4):
                next_x = cur_x + dx[i]
                next_y = cur_y + dy[i]

                if 0 <= next_x < y_len and 0 <= next_y < x_len and grid[next_x][next_y] == '1' and not visited[next_x][next_y]:
                    visited[next_x][next_y] = True
                    queue.append((next_x, next_y))

    for x in range(y_len):
        for y in range(x_len):
            if grid[x][y] == '1' and not visited[x][y]:
                bfs(x, y)
                island_number += 1

    return island_number