[PS] BOJ2178 미로탐색 ( BFS ) With 파이썬

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

2178번: 미로 탐색

 

 

◎ 문제풀이

가중치 없는 그래프에서 최단거리를 구하는 문제는 BFS로 푼다. DFS는 깊이우선탐색으로 최악의 경우를 먼저 탐색할 가능성이 있어서 처리시간이 오래 걸린다. 넓이 우선 탐색으로 해야 최악의 경우를 사전에 방지할 수 있다. 

 

◎ 코드

 

Python

#BOJ2178 미로탐색 (bfs)

import sys
from collections import deque
input = sys.stdin.readline

n,m = map(int,input().split())
miro = [ list(map(int,input().rstrip("\n"))) for _ in range(n) ] #미로 그래프
cost = [ [100001] *m for _ in range(n)] #비용 그래프

# 상하좌우 이동
dx = [0,0,1,-1]
dy = [1,-1,0,0]

#유효성검사
def isvalidate(x,y) :
  return True if x>=0 and y>=0 and x<m and y<n else False

def bfs(q) :
  while q :
    qv = q.popleft()
    x,y,cost_now = qv[0],qv[1],qv[2]

    for i in range(4) :
      nx = x + dx[i]
      ny = y + dy[i]
      cost_next = cost_now+1

      if isvalidate(nx,ny) and miro[ny][nx] == 1 :
        if cost[ny][nx] > cost_next :  # 누군가가 본인보다 낮은비용으로 접근했다면 탐색정지
          cost[ny][nx] = cost_next
          q.append((nx,ny,cost_next))

q = deque()
q.append((0,0,1))
bfs(q) #넓이우선탐색 시작
print(cost[n-1][m-1])