Coding Tests

Game Map Shortest Path

Programmers 1844 · Original problem ↗ BFS · Queue · Shortest path

In Programmers “게임 맵 최단거리,” move in four directions through cells marked 1, from the top-left corner to the bottom-right. Return the number of cells, including both endpoints, rather than the number of moves. Return -1 if the goal is unreachable.

This experiment uses a small map created for the guide. Play it to the end, then click cells to block a route. Numbers on discovered cells are shortest distances from the start.

INTERACTIVE LABShortest paths with BFS

Current state

How the solution works

  1. Set the starting distance to 1 and enqueue the start. Other distances begin at -1.
  2. Remove the front cell. Give each walkable, undiscovered neighbor a distance of current distance + 1.
  3. Append those neighbors to the queue. When the goal is removed, return its distance.
  4. If the queue empties without reaching the goal, return -1.

Every move has equal cost, so BFS discovers cells in increasing distance: 1, 2, 3 and so on. All shorter-distance cells are processed before a cell at distance d, making its first recorded distance optimal. The first path found by DFS has no such guarantee.

The custom example needs 9 cells: eight moves plus the starting cell. Green cells show one shortest path reconstructed from parent pointers.

Complexity and pitfalls

Each cell in an R × C map enters the queue once. Time and extra space are both O(RC). Python’s deque.popleft() avoids the repeated element shifting caused by list.pop(0).

Rows and columns may have different lengths. A separate distance array preserves the input map. This BFS cannot be used unchanged when moves have different costs. Playback history is extra work performed by the visualizer, not by the solution.

Solution code written for this guide

Python 3 
from collections import deque


def solution(maps):
    rows, cols = len(maps), len(maps[0])
    if maps[0][0] == 0 or maps[-1][-1] == 0:
        return -1
    distance = [[-1] * cols for _ in range(rows)]
    distance[0][0] = 1
    queue = deque([(0, 0)])
    while queue:
        r, c = queue.popleft()
        if r == rows - 1 and c == cols - 1:
            return distance[r][c]
        for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and maps[nr][nc] == 1 and distance[nr][nc] == -1):
                distance[nr][nc] = distance[r][c] + 1
                queue.append((nr, nc))
    return -1

References and further experiments