https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=python3

shortest_map.py

from __future__ import annotations

from collections import deque
from dataclasses import dataclass
from enum import IntEnum
from functools import cached_property
from typing import List, Tuple

Grid = List[List[int]]


class MapType(IntEnum):
    Wall = 0
    Unvisited = 1


@dataclass
class Point:
    x: int
    y: int

    def __add__(self, other: Point):
        return Point(self.x + other.x, self.y + other.y)


FAIL = -1
DIRS = (Point(0, 1), Point(1, 0), Point(0, -1), Point(-1, 0))


@dataclass
class Program:
    maps: Grid

    def __getitem__(self, p: Point) -> int:
        return self.maps[p.y][p.x]

    def __setitem__(self, p: Point, value: int):
        self.maps[p.y][p.x] = value

    @cached_property
    def width(self) -> int:
        return len(self.maps[0])

    @cached_property
    def height(self) -> int:
        return len(self.maps)

    @cached_property
    def begin(self) -> Point:
        return Point(0, 0)

    @cached_property
    def end(self) -> Point:
        return Point(self.width - 1, self.height - 1)

    def is_first_visit(self, p: Point) -> bool:
        return (
            0 <= p.x < self.width
            and 0 <= p.y < self.height
            and self[p] == MapType.Unvisited
        )

    def get_candidates(self, p: Point) -> Tuple[Point, ...]:
        return tuple(p + d for d in DIRS if self.is_first_visit(p + d))

    def bfs(self) -> int:
        queue = deque((self.begin,))

        while True:
            p = queue.popleft()

            if p == self.end:
                return self[self.end]

            candidates = self.get_candidates(p)
            if len(candidates) == 0 and len(queue) == 0:
                return FAIL

            for d in candidates:
                self[d] = self[p] + 1
                queue.append(d)




def solution(maps: Grid) -> int:
    return Program(maps).bfs()


ok = [
    [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],
]
fail = [
    [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],
]


if __name__ == "__main__":
    print(solution(ok))
    print(solution(fail))