#2178 미로탐색

백준 #2178  미로탐색

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

 

 

 

처음짠코드

BFS로

1인 칸들을 큐를 활용하여 너비우선 탐색 구현에는 성공했으나...

그냥 순서대로 길을 탐색하기만 했고 그 중 최종 위치까지의 최단경로를 찾는 방법을 몰랐다!

count로 +1 하다보니 그냥 갈수있는 칸, 1의 갯수가 나왔다

 

 

---

 

 

정답

이전 코드에서는 check를 단지 이전에 방문한 적 있는지 없는지를 알아내는데 사용했는데

여기선 용도를 바꿨다.

 

check 일단 0으로 초기화

check[0][0]  = 1 즉 시작점을 1로 함

이후 다음 탐색하면서 1씩 더한다.

그럼 해당 칸 까지 도달하는데 몇 칸을 거쳤는지 알 수 있음!!!!!!!

우리는 항상 배열의 마지막 칸 까지 가기 때문에 더욱 수월하다

(이전에 간 적 없는 길인지 확인하는 방법으 전과 같이 check == 0 로 알아낼 수 있다)

from collections import deque

n, m = map(int, input().split())
maze = [list(map(int, input())) for _ in range(n)]
check = [[0 for _ in range(m)] for _ in range(n)]

#상하좌우
x = [1,-1,0,0]
y = [0,0,-1,1]

q = deque([[0,0]])
check[0][0] = 1

while q:
    now = q.popleft()

    for i in range(4):
        next_x = now[0] + x[i]
        next_y = now[1] + y[i]

        if 0 <= next_x < n and 0 <= next_y < m:
            if maze[next_x][next_y] == 1 and check[next_x][next_y] == 0:
                q.append([next_x, next_y])

                check[next_x][next_y] = check[now[0]][now[1]]+1

print(check[n-1][m-1])