[BFS] 백준 2178번 미로 탐색 [Python]

from collections import deque

def makeKey(x ,y):
  return "{}{}{}".format(x, ",", y)

str = input().split(' ')
n = int(str[0])
m = int(str[1])
dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)

map = [list(map(int, list(input()))) for i in range(n)]
print(map[6][0])
visit = [[0 for i in range(m)] for i in range(n)]
distance = dict()

x = 0
y = 0

que = deque()
que.append([x, y])
visit[x][y] = 1
distance[makeKey(x, y)] = 1

while True:
  np = que.popleft()
  nx = np[0]
  ny = np[1]
  
  if nx == n - 1 and ny == m - 1:
    break
  
  for i in range(len(dx)):
    pp = [nx + dx[i], ny + dy[i]]
    px = pp[0]
    py = pp[1]
    if px < 0 or px > n-1 or py < 0 or py > m-1: continue
    
    if visit[px][py] == 0:
      visit[px][py] = 1
      if px == 1 and py == 0:
        print()
      if map[px][py] == 1:
        que.append([px, py])
        if makeKey(px, py) not in distance:
          distance[makeKey(px, py)] = distance[makeKey(np[0], np[1])] + 1
        else:
          distance[makeKey(px, py)] = min(distance[makeKey(px, py)], distance[makeKey(np[0], np[1])] + 1)
  
print(distance[makeKey(n-1, m-1)])

 

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

 

기초적인 BFS문제로

키 포인트는 좌표 별 최소 거리값을 저장하는 것이다.

 

x, y좌표를 키값으로 하고 int 값을 갖고 있는 HashMap에 distance 인스턴스에

키: x,y 좌표

값: 해당 좌표의 최소 거리

형태로 저장해 관리했다.