# 테페리넷

## 테페리넷

### 관리자 전용

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)
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) - 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

### 문서 도구 