미로 탈출

책 " 이것이 코딩테스트다 with 파이썬" 연습

문제

💡 문제

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

---

📌 입력 조건

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

---

🔐 출력 조건

- 첫째 줄에 최소 이동 칸의 개수를 출력한다.
ex)
	5 6
    101010
    111111
    000001
    111111
    111111 출력: 10 

🥔 해결

from collections import deque

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

lists = []

for i in range(n):
 lists.append(list(map(int, input())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def solution(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 == n or ny == m or  nx == -1 or ny == -1:
             continue
         
         if lists[nx][ny] == 0:
             continue
         
         if lists[nx][ny] == 1:
             lists[nx][ny] = lists[x][y] + 1
             queue.append((nx, ny))
         
             
 return lists[n-1][m-1]

print(solution(0, 0))

이 문제는 BFS를 써주는 식 이였다.

역시 이 문제도 dx dy를 쓴 후 nx = x + dx[i] 식으로 방향에 따라서 만들어줬다.

처음에는 그러면 (0,0)이 또 들어가기 때문에, 문제가 생길것이라고 판단했으나,

애초에 if lists[nx][ny] == 1로 작성했기 때문에 이미 3으로
변경된 (0, 0) 자리가 append() 될리가 없었다.

그 후 맨 끝자리의 값을 return 하는 식으로 마무리!

특히 print()는 원하는 값을 출력하기 위해서는 무조건 (0, 0)으로 넣어줘야 했다.