DFS/BFS - 음료수 얼려 먹기, 미로탈출

---

음료수 얼려먹기

def dfs(x, y):
    if x <= -1 or x >= n or y <= -1 or y>= m:
        return False
    
    if graph[x][y] == 0:
        graph[x][y] = 1
        
        dfs(x-1, y) #True or False
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        return True
    return False

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

graph = []
for i in range(n):
    graph.append(list(map(int, input())))
    
result = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            result += 1
            
print(result)

 

DFS를 재귀적으로 나타냈다.

기초적인 부분이 부족해서 이해가 안됐는데

함수안에 있는 함수 즉 재귀함수에 관한 것과 함수의 종료 조건에 관한 것이었다.

dfs()안에 있는 dfs()의 결과로 True/False가 나올 뿐 함수는 종료되지 않는다는 점과 for문에서 수행한 dfs()에서 하나의 값만이 나온다는 점이다.

 

---

미로탈출

from collections import deque

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 nx >= n or ny < 0 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]

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]

print(bfs(0,0))

 

미로를 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하는 문제.

즉 최소 거리를 구하는 문제다.

각 그래프 노드에 출발 지점부터의 거리를 저장하는 idea.

이동할 방향(상, 하, 좌, 우)을 리스트로 미리 만들어 놓고 써먹는 idea.

 

각 좌표에서 상하좌우로 탐색을 진행하면서 이웃 노드가 나아갈 수 있는 길이라면(1) 이전 노드까지의 거리에 +1을 하여 해당 노드에 저장하는 방식으로 진행한다.