미로 탈출 (DFS,BFS/실전)

미로 탈출

N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

 

입력 조건

첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

 

출력 조건

첫째 줄에 최소 이동 칸의 개수를 출력한다.

 

입력

5 6
101010
111111
000001
111111
111111

 

출력

10

 

 

---

 

문제 해설

아직 알고리즘의 세계는 멀고 험하다... 하나씩 증가시켜서 최단거리를 재는 방식은 생각하고 있었는데, bfs를 통해 그런 구현을 하는게 너무 어려웠당.. 애초에 while queue: 라는 구조가 아직 머리에 잘 안익어서 그런것같기도..

오늘은 bfs랑 dfs 문제좀 많이 풀어봐야지 32~35라인부분이 가장 어려웠다.

 

---

코드

from collections import deque

#행렬 받아오기
n, m = map(int, input().split())

#2차원 배열 받아오기
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
            #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))