백준 2178(미로 탐색) - Python(파이썬) - BFS

2178번: 미로 탐색

 

예제 설명

 

이런식으로 문제에서 주어진 배열에 1이 적혀있고 인접한 칸으로만 이동이 가능하다.

따라서 BFS 문제로 문제는 이동할때마다 이동한 곳(array[y][x])의 값보다 +1시켜서 마지막 array[4-1][6-1]의 값을 구하면 된다.

( https://coooco.tistory.com/32 )

 

💻 Python

처음 한 풀이

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().split())
array=[[] for _ in range(n)]

#띄어쓰기 없는 아이들 입력 받기
for i in range(n):
    str = sys.stdin.readline().strip()
    for j in range(m):
        array[i].append(int(str[j]))

#d가 갈 수 있는 범위
d = [[1,0],[0,1],[-1,0],[0,-1]]
#bfs
def bfs(y,x):
    queue = deque()
    queue.append((y,x))
    while queue:
        y1,x1 = queue.popleft()
        for dx,dy in d:
            if 0<=y1+dy<n and 0<=x1+dx<m:
                if array[y1+dy][x1+dx]==1:
                    array[y1+dy][x1+dx]=array[y1][x1]+1
                    queue.append((y1+dy,x1+dx))


#(1,1)에서 처음 시작하므로
bfs(0,0)
print(array[n-1][m-1])

---

정리한 풀이

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().split())
array=[]

for i in range(n):
    array.append(list(map(int,sys.stdin.readline().strip())))
    
d = [[1,0],[0,1],[-1,0],[0,-1]]

def bfs(y,x):
    queue = deque()
    queue.append((y,x))
    while queue:
        y1,x1 = queue.popleft()
        for dx,dy in d:
            if 0<=y1+dy<n and 0<=x1+dx<m:
                if array[y1+dy][x1+dx]==1:
                    array[y1+dy][x1+dx]=array[y1][x1]+1
                    queue.append((y1+dy,x1+dx))


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