사용자 도구

사이트 도구


ps:problems:programmers:1844

게임 맵 최단거리

ps
링크https://programmers.co.kr/learn/courses/30/lessons/1844
출처프로그래머스
문제 번호1844
문제명게임 맵 최단거리
레벨Level 4
분류

그래프, BFS

시간복잡도O(nm)
인풋사이즈n<=100, m<=100
사용한 언어Python
해결날짜2021/01/22

풀이

  • 그냥 전형적인 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

토론

댓글을 입력하세요:
Q Y W N A
 
ps/problems/programmers/1844.txt · 마지막으로 수정됨: 2021/01/22 06:32 저자 teferi