2차원 배열 상에서 최단거리 구하기 -> queue를 활용한 BFS
from collections import deque
def bfs(x, y, maps, n, m):
q = deque()
q.append((x, y)) # 시작위치 (0, 0) 넣기
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while q: # queue가 비어있지 않는 동안 계속 반복 (비어있게 된다는 것은 더 이동할 수 있는 곳이 없다는 의미이므로 종료)
x, y = q.popleft() # queue(다음에 방문해야 할 좌표 누적되어있음)에서 선입선출함
for i in range(4): # 상하좌우 모두 고려함
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m: # 맵을 벗어나면 패스
continue
if maps[nx][ny] == 0: # 벽이면 못가서 패스
continue
if maps[nx][ny] == 1: # 갈 수 있는데 아직 방문 안한 곳이라면 감
maps[nx][ny] = maps[x][y] + 1 # 방문한 곳에 현재까지 거리 + 1해서 누적 거리 표시
q.append((nx, ny)) # 다음에 방문하기 위해 queue에 넣어줌
return maps[n - 1][m - 1] # 상대 팀 진영 칸에 적힌 숫자가 최단 거리이므로
def solution(maps):
answer = 0
n = len(maps) # maps의 행 크기
m = len(maps[0]) # maps의 열 크기
answer = bfs(0, 0, maps, n, m)
if answer == 1: # 만약 상대 팀 진영에 도달하지 못했다면 해당 칸에 1이 써있을 것이므로
answer = -1 # -1 리턴하기
return answer