https://school.programmers.co.kr/learn/courses/30/lessons/1844
BFS 알고리즘으로 풀이하였다. 상, 하, 좌, 우로 이동할 때의 좌표 변화 값을 dx, dy 배열을 활용해 각각 저장한 후, 사용자의 좌표를 움직여보면서 이동 가능할 때 이동을 진행한다.
maps 배열에 사용자가 한 칸씩 이동할 때마다 배열 값을 1씩 증가하여 기록하면서 최종적으로 도착 지점에 도착했을 때의 이동 횟수를 정답으로 리턴한다.
만약 최종 목적지에 도달하지 못한다면 -1을 리턴한다.
from collections import deque
def solution(maps):
answer = 0
n, m = len(maps), len(maps[0])
visited = [[0]*m for _ in range(n)]
answer = bfs(maps, visited, 0, 0)
return answer
def bfs(maps, visited, x, y):
n, m = len(maps), len(maps[0])
dx = [0, 0, -1, 1] # 상하좌우
dy = [-1, 1, 0, 0]
queue = deque()
queue.append((x, y))
visited[x][y] = 1
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= 0 and nx < n and ny >= 0 and ny < m:
if maps[nx][ny] == 1 and visited[nx][ny] == 0:
maps[nx][ny] = maps[x][y]+1
queue.append((nx, ny))
visited[nx][ny] = 1
if maps[n-1][m-1] == 1:
return -1
else:
return maps[n-1][m-1]
결과 실행 화면