[백준] 2178번 미로탐색 (bfs, python)

728x90
반응형

www.acmicpc.net/problem/2178

 

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

최소 경로를 bfs로 찾는 법 

from collections import deque

def bfs():
    dq=deque()
    dq.append((0,0))
    vis[0][0]=1
    cnt=1
    while dq:
        x,y=dq.popleft()
        if x==n-1 and y==m-1:
            return vis[x][y]
        for k in range(4):
            xx,yy=x+dx[k],y+dy[k]
            if xx<0 or xx>=n or yy<0 or yy>=m: continue
            if vis[xx][yy]: continue
            if a[xx][yy]=='1':
                vis[xx][yy]=vis[x][y]+1
                dq.append((xx,yy))
    


dx,dy=[1,-1,0,0],[0,0,1,-1]

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

a=[list(input()) for _ in range(n)]
vis=[[0]*m for _ in range(n)]
print(bfs())
728x90
반응형

'백준' 카테고리의 다른 글

[백준] 13549번 숨바꼭질 3 (python, bfs)  (0) 2020.10.16
[백준] 12851번 숨바꼭질 2 (bfs, 파이썬)  (1) 2020.10.16
[백준] 1516번 게임개발 (파이썬, 위상정렬, 골드3)  (0) 2020.10.10
[백준] 2056번 작업 (파이썬, 위상정렬)  (0) 2020.10.10
[백준] 1766번 문제집 (위상정렬, 우선순위큐, 파이썬)  (0) 2020.10.10
TAGS.

Comments