📌 DFS & BFS 기초 문제 풀이 (이것이 취업을 위한 코딩 테스트다 with python)

📖 01. <문제> 음료수 얼려 먹기

✏️ 문제

🕶️ 해설

✍️ 입력

def dfs(x, y):
    if x < 0 or y < 0 or x >= N or y >= M:
        return False
    
    if grahp[x][y] == 0:

        grahp[x][y] = 1

        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False

N, M = map(int, input().split())
result = 0

grahp = []
for i in range(N):
    grahp.append(list(map(int, input())))

print(grahp)

for i in range(N):
    for j in range(M):
        if dfs(i, j) == True:
            result += 1

print(result)

💻 출력
> 4 5
00110
00011
11111
00000

3

📖 02. <문제> 미로 탈출

✏️ 문제

🕶️ 해설

✍️ 입력

from collections import deque

n, m = map(int,input().split())

graph = []
for i in range(n):
    graph.append(list(map(int, input())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))

    return graph[n - 1][m - 1]
    
print(bfs(0,0))
    

💻 출력
>3 3
110
010
011

5

[출처] 이것이 취업을 위한 코딩테스트다. with python (나동빈 지음)