[Python] 프로그래머스(Lv2) - 게임 맵 최단거리
안녕하세요 !
https://programmers.co.kr/learn/courses/30/lessons/1844
프로그래머스 게임 맵 최단거리 문제입니다.
답이 되는 최단거리
풀이
최단거리를 구하는 문제로 BFS로 풀 수 있습니다.
먼저, maps 배열을 0으로 둘러싸줍니다. while q 안에서 배열 밖을 벗어났는지 체크하는 걸 안하기 위해서 0으로 둘러싸줬습니다.
check 배열을 만들어 0으로 초기화 합니다. 0이라면 아직 지나지 않은 위치가 됩니다.
q로 너비탐색을 하면서 현재좌표가 (n, m) 이라면 return 해줍니다.
from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def solution(maps):
q = deque()
n = len(maps)
m = len(maps[0])
maps = [[0] + r + [0] for r in maps]
maps = [[0] * (m + 2)] + maps
maps += [[0] * (m + 2)]
q.append([1, 1])
check = [[0] * len(maps[0]) for _ in range(len(maps))]
check[1][1] = 1
while q:
x, y = q.popleft()
if x == n and y == m:
return check[n][m]
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if check[nx][ny] == 0 and maps[nx][ny] == 1:
q.append([nx, ny])
check[nx][ny] = check[x][y] + 1
return -1
Author And Source
이 문제에 관하여([Python] 프로그래머스(Lv2) - 게임 맵 최단거리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kerri/Python-프로그래머스Lv2-게임-맵-최단거리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)