[이코테][Chapter 5][문제] 4. 미로 탈출

[문제설명]

N by M 크기의 직사각형 형태의 미로에 갇혀있다. 미로에는 괴물이 있어 이를 피해서 탈출해야 한다. 유저의 초기 위치는 (1, 1)이고 미로의 출구는 (N, M) 위치에 존재하며 한 번에 한 칸 씩 이동이 가능하다. 이 때 괴물이 있는 부분은 0, 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이 때 유저가 미로를 탈출하기 위해 움직여야 할 최소 칸의 개수를 구해라. 단, 칸을 셀 때 시작, 마지막 칸도 포함시켜야 한다.

[입력조건]

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

[출력조건]

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

---

BFS의 기본 문제입니다. 저는 못풀었지만 연습이므로 풀이를 봐봤어요.

사고 과정은 다음과 같습니다.

1. 위, 아래, 좌, 우 네 방향으로 움직일 수 있다.

2. BFS로 접근하여, 한 칸씩 움직일 때 마다 숫자를 1씩 증가 시킨다.

3. 마지막 칸인 [n-1][m-1]에 있는 숫자를 반환한다.

 

아직은 처음이라 사고 과정을 봐도 구현을 할 수 있을지는 의문인데.. 많은 문제를 풀어봐야 겠어요.

from collections import deque

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
            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]
            
n,m = map(int, input().split())
graph = []
for _ in range(n):
    row = list(map(int, input().split()))
    graph.append(row)

print(bfs(0,0))