미로 탈출[DFS/BFS] #이것이 코딩테스트다

[문제] 음료수 얼려먹기: 문제 설명

N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다.

현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다.

괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다.

미로는 반드시 탈출할 수 있는 형태로 제시된다.

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

칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

난이도: ●◐○| 풀이시간 30m | 시간제한 1초 | 메모리 128mb

 

<input case>

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

 

 

<Output case>

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

input example	Output example
5 6 101010 111111 000001 111111 111111	10

<Idea>

Q1. 이 문제는 미로에서 빠져나가는게 목표니까 깊이 우선 탐색을 하는 편이 이득이겠네
A. 맞지 그럼 이 문제를 풀려면 방향도 부여를 해야하고, 이 값이 판 외부로 벗어나지 않게 해야하네

 

from collections import deque

n,m=map(int,input().split())
table=[]
now= [0,0]
dir=[(0,-1),(-1,0),(0,1),(1,0)]
count=1
queue=deque()

for _ in range(n):
  table.append(list(map(int,input().split())))


while True:
  for row, col in dir:
    if now[0] + row > n-1 or now[0] + row < 0 or now[1] + col > m-1 or now[1] + col < 0 or table[now[0]+ row][now[1]+ col] <= 0:  continue #이미 방문 했었거나 인덱스 범위 밖의 값은 배제해줍니다.
    queue.append([now[0]+row, now[1]+col, count+1] )
    
  table[now[0]][now[1]] = -1 #방문 처리
  now=queue.popleft() #큐의 첫 값을 다시 가져옵니다.
  count=now[2]
  if now[0] == n-1 and now[1] == m-1:
    print(count)
    break