[BFS 알고리즘] 미로 탈출 - 파이썬(python)

미로 탈출

난이도 : 中下 풀이 시간 : 30분

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

해답

 

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

            elif (graph[nx][ny] == 0):
                continue

            elif (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))

---

예시

 

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))

---

해설

 

먼저 n, m, graph에 입력을 받습니다. dx, dy에 상하좌우로 이동할 때 계산할 방향을 지정합니다.
이 문제는 bfs 알고리즘을 사용합니다. 그러므로 bfs 함수를 하나 정의해줍니다.
deque 라이브러리를 사용하여 queue 변수에 큐 자료구조를 지정해줍니다.
queue에 append() 함수로 시작 지점을 정의해주고, while 반복문으로 queue가 빌 때 까지 반복해줍니다.
for 반복문으로 상하좌우의 좌표를 한 번씩 계산해줍니다. 공간을 벗어나거나 상하좌우가 벽(0)이라면 continue로 해당 과정을 무시해주고 다시 반복문을 돌려줍니다.
만약 상하좌우를 반복할 때 범위 안에 존재하고 1의 값을 가진다면, 이전 칸의 값에 +1을 더해줍니다.
이와 같은 과정을 반복하면 오른쪽 가장 아래 칸(미로의 출구)에는 이동한 횟수가 저장됩니다.
그러므로 while 반복문에서 graph[n-1][m-1]에 해당하는 값을 return해줍니다.