[baekjoon] 백준 2178번 : 미로 탐색 (by python 파이썬) with bnf

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

정답 code

#미로 탐색
from collections import deque

def bfs(x,y):
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    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 nx>=n or ny<0 or ny >= m:
                continue

            if miro[nx][ny] == 0:
                continue

            if miro[nx][ny] == 1:
                miro[nx][ny] = miro[x][y] + 1
                queue.append((nx,ny))

    return miro[n-1][m-1]


n, m = map(int,input().split())

miro = [list(map(int,input())) for _ in range(n)]
print(bfs(0,0))

 

이번문제는 전에도 많이 다뤘던 너비 우선탐색 bfs 유형의 문제였다.

 

주어진 입력을 받고 bnf함수를 만들어 구동하면 된다.

 

solution

deque를 이용하여 처음을 데큐에 추가한뒤에 좌표를 이동해가며 이동 가능한 좌표일때 해당 좌표에 전 좌표에서 1을 추가한다음 데큐에 다시 넣는다.

이런식으로 이동가능한 좌표를 너비 우선탐색으로 찾아가며 경우의수를 입력해준다.

 

데큐가 비어있게 되면 도착지점에 저장된 경우의수를 출력해준다.