[LeetCode] 200. Number of Islands (Daily Question)

문제

---

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

바다를 의미하는 0과 섬의 땅을 의미하는 1로 구성된 2차원 배열 grid가 주어졌을 때, 섬 해안선의 길이를 구하는 문제이다.

 

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

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

 

풀이

---

아이디어

좌상단(0, 0)부터 우하단까지 2중 for문으로 탐색하며 섬 발견 시 BFS로 탐색하고, 해당 섬을 없애버린다.

 

코드

class Solution:
    # 한 섬의 모든 땅을 탐색하고 지도에서 지워버림
    def explore(self, poss):
        # 다음 번에 탐색할 위치들을 저장
        # 같은 위치를 저장하지 않기 위해 set 사용
        next_poss = set([])

        for pos in poss:
            x, y = pos
            self.grid[x][y] = "0"
            
            # 위쪽 탐색
            if x-1 >= 0 and self.grid[x-1][y]=="1": 
                next_poss.add((x-1, y))

            # 아래쪽 탐색
            if x+1 < len(self.grid) and self.grid[x+1][y]=="1": 
                next_poss.add((x+1, y))

            # 왼쪽 탐색
            if y-1 >= 0 and self.grid[x][y-1]=="1": 
                next_poss.add((x, y-1))

            # 오른쪽 탐색
            if y+1 < len(self.grid[0]) and self.grid[x][y+1]=="1": 
                next_poss.add((x, y+1))
        
        if next_poss:self.explore(list(next_poss))

    def numIslands(self, grid: List[List[str]]) -> int:
        self.grid = grid

        answer = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # 섬을 발견했을 때 해당 섬의 모든 땅 탐색
                if self.grid[i][j]=="1": 
                    self.explore([(i, j)])
                    answer += 1

        return answer

---

 

후기

---

난이도

너비/깊이 우선 탐색 기초 문제라고 할 수 있다.

알고리즘 기법을 알고 있다면 쉽게 풀 수 있는 문제이다.

시간조건이 널널하고 예외가 없으므로 까다롭지는 않았다.

다른 풀이

DFS로 가능하다.