항해99 2주차 - 섬의개수

Today I learned
2022/01/20

회고록

---

1/20

항해 99, 알고리즘 1주차

교재 : 파이썬 알고리즘 인터뷰

12장 그래프

1. 이론

https://velog.io/@jsw4215/%ED%95%AD%ED%95%B499-2%EC%A3%BC%EC%B0%A8-%EA%B7%B8%EB%9E%98%ED%94%84DFSBFS-%EC%9D%B4%EB%A1%A0-%EC%A0%95%EB%A6%AC

2. 문제

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.

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

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

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

3. MySol

• Recursive

def solution(grid):

    result = []
    rows = len(grid)
    cols = len(grid[0])
    px = [-1,1,0,0]
    py = [0,0,-1,1]
    count = 0

    def isLandDfs(x, y):

        grid[y][x] = "0"
        for i in range(4):
            nx = px[i] + x
            ny = py[i] + y
            # 조건들

            if nx < 0 or ny < 0 or nx >= cols or ny >= rows:
                print("e")
                continue
            print('[nx] :' + str(nx) + ', [ny]: ' + str(ny))
            if grid[ny][nx] == "0":
                continue


            isLandDfs(nx,ny)


    for x in range(cols):
        for y in range(rows):

            if grid[y][x] == "0":
                continue

            count+=1

            isLandDfs(x,y)

    return count

if __name__ == '__main__':

    grid = [
        ["1", "1", "0", "0", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "1", "0", "0"],
        ["0", "0", "0", "1", "1"]
    ]

    result = solution(grid)

    print('result : ' + str(result))

• Stack(DFS)

def solution(grid):

    result = []
    rows = len(grid)
    cols = len(grid[0])
    px = [-1,1,0,0]
    py = [0,0,-1,1]
    count = 0
    stack = []

    for x in range(rows):
        for y in range(cols):

            if grid[x][y] == "0":
                continue
            count+=1
            stack.append((x,y))
            while stack:
                x, y = stack.pop()

                grid[x][y] = "0"

                for i in range(4):
                    nx = px[i]+x
                    ny = py[i]+y
                    print("nx : " + str(nx) + ", ny : " + str(ny))
                    if nx < 0 or ny < 0 or nx >= rows or ny >= cols or grid[nx][ny]=="0":
                        continue

                    stack.append((nx,ny))

    return count

if __name__ == '__main__':

    grid = [
        ["1", "1", "0", "0", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "1", "0", "0"],
        ["0", "0", "0", "1", "1"]
    ]

    result = solution(grid)

    print('result : ' + str(result))

4. 배운 점

• 재귀함수에 대한 이해
• DFS에 대한 이해

5. 총평

재귀, DFS 훈련