[코테] DFS/BFS 문제풀기 - 미로 탈출

Day10

DFS/BFS 문제풀기 - 미로풀기 (난이도 중하)

 

<문제>

N X M 크기의 직사각형 미로에 갖혀 있는데 (1,1) 위치에서부터 (N,M) 출구까지 이동한다. 괴물이 있는 0, 괴물이 없는 1로 이루어진 미로를 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하자.

 

<조건>

첫째 줄 : N(4≤N)과 M(M≤200)

N줄 : M개의 정수(0 또는 1). 공백없이.

시작 칸과 마지막 칸은 항상 1

 

미로 탈출 풀이

#솔루션

from collections import deque

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

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

direction = [(-1,0), (1, 0), (0, -1), (0, 1)]
#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 + direction[i][0] # nx = x + dx[i]
            ny = y + direction[i][1] # ny = y + dy[i]

            # 범위 벗어나면 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            # 벽이면 무시
            if world[nx][ny] == 0:
                continue
            # 처음 방문하는 노드인 경우에만 최단 거리 기록
            if world[nx][ny] == 1:
                world[nx][ny] = world[x][y] + 1
                queue.append((nx, ny))
    # 가장 오른쪽 아래까지의 최단 거리
    return world[n-1][m-1]

print(bfs(0,0))

BFS를 이용해서 시작한 곳에서 가까운 노드들부터 차례로 탐색한다.

 

#1

#2