[알고리즘] 프로그래머스 - 게임 맵 최단거리

June·2021년 3월 5일
0

알고리즘

목록 보기
119/260

프로그래머스 - 게임 맵 최단거리

내 풀이

import sys
from collections import deque
from itertools import combinations
from itertools import permutations
import math
sys.setrecursionlimit(100000)

dx = [-1, 0, 0, 1]
dy = [0, 1, -1, 0]


def bfs(y, x, visited, maps):
    q = deque()
    q.append((y, x, 1))
    while q:
        y, x, count = q.popleft()
        visited[y][x] = 1
        if y== len(maps)-1 and x == len(maps[0])-1:
            return count

        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0<=ny<len(visited) and 0<=nx<len(visited[0]) and maps[ny][nx] != 0:
                if visited[ny][nx] == 0:
                    visited[ny][nx] = 1
                    q.append((ny, nx, count + 1))
    return -1

def solution(maps):
    visited = [[0]*len(maps[0]) for _ in range(len(maps))]
    answer = bfs(0, 0, visited, maps)
    return answer

기본적인 BFS 문제이다.

0개의 댓글