[프로그래머스] 게임 맵 최단거리.py

0,0 에서 시작해서 mapsize, mapsize 까지 가기 위한 최단거리를 구하는 문제이다.

BFS는 공식과도 같다 하여 BFS알고리즘을 검색하여 참고하여 코드를 구현 하였다.

 

# https://programmers.co.kr/learn/courses/30/lessons/1844
# BFS를 써야 풀 수 있는 문제 

from collections import deque

def nextXY(n, maps, sizeY, sizeX) :
    y = n[0]
    x = n[1]
    depth = n[2]
    nextque = []
    if y - 1>= 0 and maps[y - 1][x] != 0 : #up
        nextque.append([y - 1, x, depth + 1])
    if y + 1 < sizeY and maps[y + 1][x] != 0 : #down
        nextque.append([y + 1, x, depth + 1])
    if x + 1 < sizeX and maps[y][x + 1] != 0 : #right
        nextque.append([y, x + 1, depth + 1])
    if x - 1 >= 0 and maps[y][x - 1] != 0  : #left
        nextque.append([y, x - 1, depth + 1])
    return nextque

def isFinish(y, x, sizeY, sizeX) :
    if y == sizeY -1  and x == sizeX - 1 :
        return True
    else :
        return False

def solution(maps):
    queue = deque([[0,0,1]])
    sizeY = len(maps)
    sizeX = len(maps[0])
    while queue :
        n = queue.popleft()
        if maps[n[0]][n[1]] != 0 :
            if isFinish(n[0], n[1], sizeY, sizeX) :
                return n[2]
            maps[n[0]][n[1]] = 0
            queue +=  nextXY(n, maps, sizeY, sizeX)
        print(queue)
    return -1


print(solution([[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]))
print(solution([[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]))

 

https://cyc1am3n.github.io/2019/04/26/bfs_dfs_with_python.html

[Daily PS] 파이썬으로 구현하는 BFS와 DFS