[2178] 미로탐색 In python

> BFS

 

처음에 떠올렸던 생각은 다이나믹 프로그래밍

 

근데 지나야하는 최소의 칸 수를 구해야하므로

BFS로 풀었음.

 

문제에서 주어진 예제 2번의 과정을 풀어보았음.

 

 

 

그림이 좀 지저분하긴 한데..

일단 노란색 형광펜으로 쳐져있는 길로 가야 

최소의 이동칸 수를 구할 수 있다.

 

오른쪽에 써있는 작대기 + 숫자는 -> 이동순서

 

 

여기서 현재 위치란 nx,ny (x,y에서 이동한 값)

 

1. 만약 길이라면?

1.1 방문한 적이 없는 경우라면?

1.1.1 큐에 현재 위치 append

1.1.2 현재 위치 방문처리

1.1.3 answer 리스트의 현재 위치 부분에 +=1 해주기

 

1.2 방문한 적이 있는 경우라면? --> *** 이 부분이 중요 ***

1.2.1 answer[nx][ny]의 값과 answer[x][y]+1 값중에 작은 값을 answer[nx][ny]에 넣는다.

 

 

 

x=1, y=4인 경우를 살펴보자.

위로 움직일 경우 nx,ny=0,4가 된다.

array[nx][ny]가 1이므로 이동할 수 있다. -> 1번

visited[nx][ny]=False이다. -> 1.1번

(nx,ny) append -> 1.1.2번

answer[nx][ny]+=1 -> 1.1.3번

 

왼쪽으로 움직일 경우 nx,ny=1,3이 된다.

array[nx][ny]가 1이므로 이동 가능 ->. 번

visited[nx][ny]=True -> 1.2번

answer[nx][ny]=min(answer[nx][ny]+1=8, answer[nx][ny]=6)

answer[nx][ny]=6이 된다. 

 

 

from collections import deque

n, m = map(int, input().split())
array = [[] for _ in range(n)]
for i in range(n):
    for j in list(input()):
        array[i].append(int(j))
# 상,우,하,좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
answer = [[0 for _ in range(m)] for _ in range(n)]

def bfs(a,b):
    queue = deque()
    queue.append((0, 0))
    visited = [[False for _ in range(m)] for _ in range(n)]
    visited[0][0] = True
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if array[nx][ny]: # 길인 경우
                    if not visited[nx][ny]: # 방문한 적이 없는 경우
                        queue.append((nx,ny))
                        visited[nx][ny]=True
                        answer[nx][ny]+=answer[x][y]+1
                    else: # 방문한 적이 있는경우
                        answer[nx][ny]=min(answer[x][y]+1, answer[nx][ny])

bfs(0, 0)
print(answer[n-1][m-1]+1)