Today I learned
2022/01/20
회고록
항해 99, 알고리즘 1주차
교재 : 파이썬 알고리즘 인터뷰
12장 그래프
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/
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))
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))
재귀, DFS 훈련