# ์ด์ฝํ Chapter 5 DFS/BFS (4)

## Testcase 1

4 5
00110
00011
11111
00000
# 3

## Testcase 2

15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111
# 8

### Solution

• input๊ฐ ์ฌ์ด์ ๋์ด์ฐ๊ธฐ๊ฐ ์๋ค๋ ์ ์ ์ฃผ์ํ์.
์ต๊ด์ ์ผ๋ก input().split() ์ฐ์ง ๋ง๊ณ  ๋ฌธ์  ์๋ ฅ๊ฐ ํ์ธํด์ผ๊ฒ ๋ค.
• DFS = ์ฌ๊ท๋ก ๊ตฌํ!
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

for i in range(n):
for j in range(m):
if dfs(i, j) == True:
print(answer)

## ์ค์  ๋ฌธ์  2: ๋ฏธ๋ก ํ์ถ

### Testcase

5 6
101010
111111
000001
111111
111111

### Solution

• ๊ตฌํ ์๊ณ ๋ฆฌ์ฆ์ ์ํ์ข์ฐ ๋ฌธ์ ๋ ์ฝ๊ฐ ๋น์ทํ๋ค.
• BFS = deque ์ด์ฉ! (์ฌ์ค ๊ธฐ๋ณธ ๋ฆฌ์คํธ๋ก๋ ํ ์ ์๋๋ฐ, ๊ต์ฌ์์ deque์ ๊ถ์ฅํ๋ ๋ค์์๋ deque์ ์ด์ฉํด๋ณด๋๋ก ํ์)
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))

## Feedback

• ์์ง ์ค๋ ฅ์ด ๋ถ์กฑํด์ ๊ทธ๋ฐ์ง ์ค๋ ๊ณ ๋ฏผํด๋ ๊ตฌํ์ด๋ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ด ์๋ ๊ฒฝ์ฐ ํ์ด๊ฐ ์ ๋ ์ค๋ฅด์ง ์๋๋ค.
• ์๊ณ ๋ฆฌ์ฆ์ ์ ํ๋ณ๋ก ํ๊ธฐ ์ ์๋ ์ด๋ป๊ฒ๋  ๊ทธ๋ฅ ํ์๋ ๊ฒ ๊ฐ์๋ฐ, DFS๋ก ํ์ด์ผ ๋ผ! DP๋ก ํ์ด์ผ ๋ผ!๋ผ๋ ์๊ฐ์ด ์์ผ๋ ๋ ๋ชป ํธ๋ ๊ฒ ๊ฐ๊ธฐ๋โฆ
• PART 02๊น์ง๋ ์ ํ์ ์ตํ๋ค๋ ๋๋์ผ๋ก ๊ณต๋ถํ๊ณ , PART 03๋ถํฐ๋ ๊ณ ๋ฏผํ๋ ์๊ฐ์ ๋๋ ค๋ณด์

Source