2178

## 🔒 문제. ## 2178 미로 탐색
''' 입력 예시
## case 2.
N, M = 4, 6
t = [
110110,
110110,
111111,
111101
]


## case 3.
N, M = 2, 25
t = [
1011101110111011101110111,
1110111011101110111011101
]

## case 4.
N, M = 7, 7
t = [
1011111,
1110001,
1000001,
1000001,
1000001,
1000001,
1111111
]
'''
## case 1.
N, M = 4, 6
t = [
[101111],
[101010],
[101011],
[111011]
]

maze = []

### 미로 형태 변경 (2차원 정수인덱스 사용 위해 문자별 쪼개기 ... 자료형 : 숫자형)
for i in t:
    j = ''.join(map(str, i))
    j = list(map(int, j))
    maze.append(j)

## 상하좌우 이동값 정의 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

from collections import deque

## 답안 예시 보고 직접 작성해보기  -- https://www.youtube.com/watch?v=7C9RgOcvkvo&t=3291s 52:32~
def bfs(x, y):
    to_do = deque()
    to_do.append((x, y))  ## 할 일 : 튜플 형태로 초기값 입력

    while to_do:
        x, y = to_do.popleft()  ## 멀티 할당으로 튜플 값 그대로 할당
        
        for i in range(4):  ## 상하좌우 이동 가능한 경우 체크
            nx = x + dx[i]  ## 상하좌우별 이동한 x값
            ny = y + dy[i]  ## 상하좌우별 이동한 x값

            if nx < 0 or nx >= N or ny < 0 or ny >= M:  ## 미로를 벗어난 경우 건너뛰기
                continue
            if maze[nx][ny] == 0: ## 상하좌우 이동한 값이 0인 경우 건너뛰기
                continue
            if maze[nx][ny] == 1:  ## 상하좌우 이동한 값이 1인 경우 ... 이동으로 간주 (좌표값 +1)
                maze[nx][ny] = maze[x][y] + 1
                to_do.append((nx, ny))  ## 상하좌우 이동한 값을 할 일에 추가(이후 해당 값에서 또 상하좌우 탐색)
    
    return maze[N-1][M-1]  ## (N, M)의 좌표값 리턴

print(bfs(0, 0))