January 30, 2021
์ด์ฝํ Chapter 5 DFS/BFS (1)
์ด์ฝํ Chapter 5 DFS/BFS (2)
์ด์ฝํ Chapter 5 DFS/BFS (3)
4 5
00110
00011
11111
00000
# 3
15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111
# 8
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
def dfs(x, y):
if x < 0 or y < 0 or x >= n or y >= m:
return False
if graph[x][y] == 0:
graph[x][y] = 1
dfs(x, y + 1)
dfs(x + 1, y)
dfs(x - 1, y)
dfs(x, y - 1)
return True
return False
answer = 0
for i in range(n):
for j in range(m):
if dfs(i, j) == True:
answer += 1
print(answer)
5 6
101010
111111
000001
111111
111111
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def bfs(x, y):
queue = [(x, y)]
while queue:
x, y = queue.pop(0)
for i in range(4):
nx = x + dx[i]
ny = y + dx[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
if graph[nx][ny] == 0:
continue
elif graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((x, y))
return graph[n - 1][m - 1]
print(bfs(0, 0))
Source