인접하지 않은 섬 개수 구하기

문제

 

주어진 m x n 크기의 2D 이진 그리드 grid는 '1'로 표시된 육지와 '0'으로 표시된 물의 지도를 나타냅니다. 섬의 수를 반환하는 함수를 작성하세요. 섬은 물로 둘러싸여 있으며 수평 또는 수직으로 인접한 육지를 연결하여 형성됩니다. 그리드의 네 가장자리는 모두 물로 둘러싸여 있다고 가정할 수 있습니다.

 

Example:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

 

아주 신나고 흥미 진진한 문제네요~ 생각보다 쉽게 풀릴 것 같은데요 한 번 풀어보겠습니다.

 

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        col = len(grid[0])
        row = len(grid)
        visited = [[0 in _for range(col)]] in _ for range(row)]

        def bfs(start)
            return 1

        for i in range(row):
            for j in range(col):
                count += bfs
        return count

 

기본 틀은 위와같다.

1. visited는 이차배열로 컴프리헨션 기법을 사용해서 0으로 초기화 하도록 하자
2. BFS의 한 사이클이 완료되면 섬 1개를 반환해야한다.
3. BFS는 모든 점에서 테스트 해야하는데 여기서 반복 횟수를 줄여 성능 향상을 시킬 수 있을 것 같다.

 

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        col = len(grid[0])
        row = len(grid)
        visited = [[0 in _for range(col)]] in _ for range(row)]
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]

        def bfs(x, y):
            visited[x][y] = 1
            q = deque([[x, y]])
            while q:
                cur_x, cur_b = q.popleft()
                #이동 전략
            return 1

        for i in range(row):
            for j in range(col):
                if visited[j][i] == 0 and grid[i][j] == "1":
                    count += bfs(j, i)
        return count

 

조금 진행된 코드이다.

1. 진행 방향은 상, 하, 좌, 우가 될 것이므로 dx, dy 를 선언해준다.
2. bfs의 기본 구성을 하고 x, y 형태로 이동을 해야하므로 [x, y] 처럼 배열 형태로 묶어주자
3. bfs를 호출할때는 방문하지 않았으면서 육지인 곳만 호출하여 횟수를 줄이도록 했다

 

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        col = len(grid[0])
        row = len(grid)
        visited = [[0 for _ in range(col)] for _ in range(row)]
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        
        def bfs(y, x):
            visited[y][x] = 1
            q = deque([[y, x]])
            while q:
                cur_y, cur_x = q.popleft()
                for idx in range(4):
                    new_y = cur_y + dy[idx]
                    new_x = cur_x + dx[idx]
                    if 0 <= new_y < row and 0 <= new_x < col and grid[new_y][new_x] == "1" and visited[new_y][new_x] == 0:
                        visited[new_y][new_x] = 1
                        q.append([new_y, new_x])                             
            return 1

        for i in range(row):
            for j in range(col):
                if visited[i][j] == 0 and grid[i][j] == "1":
                    count += bfs(i, j)
        return count

 

1. 맨 아래 코드를 보면 col 값이 먼저 증가하므로 bfs(y값, x값)을 넣어준다
2. 이동전략은 for idx in range(4) 를 통해서 4방향으로 이동한다
3. 그다음 if 절에서 이동 범위가 맵을 초과하지는 않았는지, 방문한 적은 없는지, 섬이 맞는지 확인한다.

 

성공!!! 이제 BFS가 많이 익숙해져가고있다. 힘내자~!

 

감사합니다.