프로그래머스 고득점kit 게임 맵 최단거리 | Python
🔎 문제 설명
💚 Level 2
- 난이도 ★☆☆☆ - 그래프탐색 BFS
BFS를 구현할 수만 있다면 쉽게 풀 수 있는 문제!
최단거리를 구하는 일반적인 방법 중 하나로 출발지에서 목적지까지 1 를 더해가며 마지막 목적지의 거리를 구하는 방법이 있다. 이 문제는 그렇게 풀었으며, 목적지까지 가지 못하는 경우를 고려하면서 코드를 작성했다.
💻 내 코드
from collections import deque
def solution(maps):
answer = 0
n = len(maps)
m = len(maps[0])
def bfs():
dx = [0,0,1,-1]
dy = [1,-1,0,0]
queue = deque([(0,0)])
while queue:
x, y = queue.popleft()
if (x,y) == (n-1,m-1):
return maps[n-1][m-1]
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if 0<=nx<n and 0<=ny<m:
if maps[nx][ny] == 1:
maps[nx][ny] = maps[x][y]+1
queue.append((nx,ny))
# 목적지까지 가지 못한 경우
return -1
answer = bfs()
return answer
💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).