dfs로 풀어봤던 섬의 개수를 bfs로 다시 풀어봤다.

문제 링크

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

문제 정리

접근방법

  1. 시작 노드를 큐에 넣는다.
  2. 시작 노드를 기준으로 전체를 탐색한다.
  3. 큐가 있는동안 반복하여 시작 노드를 기준으로 상하좌우를 탐색해나간다.

코드 진행

  1. 상하좌우 탐색을 위한 리스트와 열의 길이 행의길이 섬의 개수를 지정해주는 변수를 생성한다.

    def island_bfs(grid):
    dx = [0, 0, -1, 1]    # 좌우
    dy = [-1, 1, 0, 0]    # 상하
    rows = len(grid)      # 열의 길이
    cols = len(grid[0])   # 행의 길이
    count = 0             # 섬의 개수

  2. 그래프 전체 탐색을 시작한다.

    # 전체 탐색 시작
    for r in range(rows):
        for c in range(cols):

  3. 육지가 아닐 경우 건너뛰어준다.

    # 육지가 아닐경우 건너뜀
            if grid[r][c] != '1':
                continue

  4. 육지일 경우에는 섬의 개수 카운트해주고 큐에 시작 노드를 넣어준다.

    #육지일 경우
            count += 1  #섬의 개수 카운트
            q = collections.deque([(r, c)]) #큐에 시작 노드 넣기