[leetcode] 200. number of Islands

🌵 문제

---

 

Number of Islands - LeetCode

 

 

🚀 풀이

---

배열을 도는데 만약 육지가 아니라면 해당하는 지점에서의 탐색을 시작하지 않고, 육지라면 탐색을 시작하여 연결된 육지를 감지, DFS가 끝난 후에 섬의 개수를 하나 증가하여 총 섬의 개수를 카운팅합니다. DFS 과정 내에서는 중복된 카운팅을 막기 위해 방문한 육지는 기존의 육지 ("1")와는 다르게 마킹을 해줍니다. (꼭 "V"가 아니어도 상관없습니다. "1"만 아니면 됩니다.) visited 배열을 이용해 방문 여부를 기록하지 않은 이유는 추가 공간을 사용하지 않고 grid 배열을 수정하는 것으로도 방문 여부 감지가 충분히 되었기 때문인데 원본 훼손의 우려가 있다면 visited를 둬서 방문 여부 마킹을 해도 좋을 것 같습니다. 

---

💡 풀이 코드는 아래와 같습니다. 

LAND = "1"
MARK = "V"

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def dfs(grid, x, y):
    if x < 0 or x > len(grid) - 1 or y < 0 or y > len(grid[0]) - 1:
        return
    if grid[x][y] != LAND:
        return
    
    grid[x][y] = MARK
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx <= len(grid) - 1 and 0 <= ny <= len(grid[0]) - 1:
            dfs(grid, nx, ny)

def numIslands(grid):
    cnt = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == LAND:
                dfs(grid, i, j)
                cnt += 1
    return cnt


print(numIslands([
    ["1","1","1","1","0"],
    ["1","1","0","1","0"],
    ["1","1","0","0","0"],
    ["0","0","0","0","0"]
]))
print(numIslands([
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
]))