게임 맵 최단거리

• 그냥 전형적인 BFS문제. 따로 신경쓸것은 없고 그냥 BFS를 적용하면 된다.
• V와 E가 모두 O(n*m) 인 형태이므로 시간 복잡도는 O(n*m)
• BFS로 순회하면서 방문하는 노드를 yields 하는 제너럴한 함수를 만들면서 구현했는데, 만들어 놓고 나니 저게 정말 다른 문제들 풀때도 유용할지에 대한 의구심이 들었다. 그래서 이 함수를 teflib에 추가하는 것은 보류..

"""Solution code for "Programmers 1844. 게임 맵 최단거리".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/1844
- Solution link: http://www.teferi.net/ps/problems/programmers/1844
"""

import collections
from typing import Generator, Sequence, Tuple, TypeVar

CellType = TypeVar('CellType')
PosType = Tuple[int, int]


def bfs_in_grid(grid: Sequence[Sequence[CellType]],
                empty: CellType,
                start: PosType) -> Generator[Tuple[PosType, int], None, None]:
    """Yields (pos, distance) pairs for nodes in BFS-order."""
    yield (start, 0)
    row_count, col_count = len(grid), len(grid[0])
    is_visited = [[False] * col_count for _ in range(row_count)]
    queue = collections.deque([(start, 0)])
    while queue:
        (r, c), dist = queue.popleft()
        for dr, dc in ((-1, 0), (0, -1), (0, 1), (1, 0)):
            nr, nc = r + dr, c + dc
            if not (0 <= nr < row_count and 0 <= nc < col_count and
                    grid[nr][nc] == empty and not is_visited[nr][nc]):
                continue
            is_visited[nr][nc] = True
            queue.append(((nr, nc), dist + 1))
            yield ((nr, nc), dist + 1)


def solution(maps):
    target = (len(maps) - 1, len(maps[0]) - 1)
    for pos, dist in bfs_in_grid(maps, empty=1, start=(0, 0)):
        if pos == target:
            return dist + 1
    return -1