DFS 문제(섬의 개수 구하기)

 

문제: 

'1'(육지)과 '0'(물)으로 구성된 지도를 나타내는 m x n 크기의 이진 격자가 주어질 때, 섬의 개수를 반환합니다.

섬은 물로 둘러싸여 있으며 인접한 땅을 가로 또는 세로로 연결하여 형성됩니다.(대각선 x)

 

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

 

1. DFS 스택방식으로 코드 구현

 

def island_dfs_stack(grid):
    #방문한 노드의 상하좌우를 살펴보기 위한 변수
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    #이차 배열의 row와 col의 길이를 담는 변수
    rows, cols = len(grid), len(grid[0])
    cnt = 0

    #전체 배열을 방문을 함.
    for row in range(rows):
        for col in range(cols):
            #섬만 볼거니까 바다가 나오면 다음꺼로 넘어감
            if grid[row][col] != '1':
                continue
                
            #섬이 나왔을때 cnt를 올려주고
            cnt += 1
            #그 섬의 위치를 저장
            stack = [(row, col)]
            
            #스택은 방문해야하할 노드를 저장함. 이때 방문해야하는 것은 하나의 섬으로 연결되어 있는 육지만을 얘기함
            #위에서 이 섬에 대해 한번 세줬기 때문에 이 섬만 바다로 바꾸면 됨
            while stack:
                #스택 마지막에 있는 노드의 row와 col값을 x, y라는 빈 변수에 저장
                x, y = stack.pop()
                #육지를 바다로 바꾸기 시작
                grid[x][y] = '0'
                #해당 노드의 상하좌우를 보는 문장
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    #방문한 노드의 상하좌우를 살피는데 배열에 크기에 벗어나거나, 육지가 아니면 스킵
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != '1':
                        continue
                    #육지면 스택에 쌓음(방문할 노드의 인덱스)
                    stack.append((nx, ny))
    return cnt


#출력 예. assert는 맞는지 아닌지를 확인하는 함수
assert island_dfs_stack(grid=[
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]) == 1
assert island_dfs_stack(grid=[
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]) == 3

 

 

2. DFS 재귀방식으로 코드 구현

def island_dfs_recursive(grid):
    #마찬가지로 상하좌우 살펴보는 변수
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    #col, row 길이
    m = len(grid)
    n = len(grid[0])

    cnt = 0

    #섬 하나를 바다로 바꾸는 함수. 밑에 for문을 먼저보고 이 함수를 보면 이해가 빠릅니다.
    def dfs_recursive(r, c):
        # 방문한 노드의 상하좌우를 살피는데 배열에 크기에 벗어나거나, 육지가 아니면 스킵
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != '1':
            return

        # 방문처리
        grid[r][c] = '0'
        #상하좌우 살펴보다가 육지 발견하면 반복
        for i in range(4):
            dfs_recursive(r + dx[i], c + dy[i])
        return
    
    #전체 배열을 방문함
    for r in range(m):
        for c in range(n):
            #node라는 빈 변수에 grid[r][c]가 1이 나올때까지 스킵
            node = grid[r][c]
            if node != '1':
                continue
            
            #node에 1이 나와 저장하면 육지 발견. 섬 하나로 간주 후, 그 섬 하나를 바다로 바꿈
            cnt += 1
            #섬 하나를 바다로 바꾸는 함수
            dfs_recursive(r, c)

    return cnt


assert island_dfs_recursive(grid=[
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]) == 1
assert island_dfs_recursive(grid=[
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]) == 3