프로그래머스 Lv.2 | Python | 게임 맵 최단거리

1. 문제 정보

프로그래머스

 

• 난이도: Lv.2

---

2. 문제 설명(요약)

게임 맵은 0과 1로 이루어진 2차원 배열이다.

• 1은 이동할 수 있는 칸
• 0은 벽이라 이동할 수 없는 칸

캐릭터는 왼쪽 위 (0, 0)에서 출발하고, 상대 팀 진영인 오른쪽 아래까지 이동해야 한다.

이때 상대 팀 진영까지 도착하는 최단 거리를 구하는 문제다. 도착할 수 없다면 -1을 반환한다.

---

3. 접근 기준

이 문제는 2차원 격자에서 최단 거리를 구하는 문제다.

각 칸에서 이동할 수 있는 방향은 다음 4가지다.

상, 하, 좌, 우

 

모든 이동 비용이 1로 동일하므로, 최단 거리는 BFS로 구하는 것이 적합하다.

DFS를 사용하면 한 경로를 끝까지 들어가기 때문에 처음 도착한 경로가 최단 거리라는 보장이 없다.

반면 BFS는 시작점에서 가까운 칸부터 차례대로 탐색하므로, 처음 목적지에 도착했을 때의 거리가 최단 거리다.

---

4. 사용한 패턴 / 알고리즘

BFS (너비 우선 탐색)

• 시작점에서 가까운 칸부터 탐색
• 최단 거리 문제에 적합
• 큐를 사용해서 탐색 순서를 관리

2차원 배열 탐색

• 행, 열 범위 체크
• 벽 여부 체크
• 방문 여부 체크

---

5. 핵심 아이디어

핵심은 maps 배열 자체에 이동 거리를 누적하는 것이다.

처음 시작 위치는 1이다. 다음 칸으로 이동할 때마다 현재 칸 값에 1을 더해서 저장한다.

예:

maps[nx][ny] = maps[x][y] + 1

 

이렇게 하면 별도의 거리 배열을 만들지 않아도 된다.

또 이미 방문한 칸은 다시 방문하지 않도록 해야 한다. 이 코드에서는 방문한 칸의 값을 거리 값으로 바꾸기 때문에, maps[nx][ny] == 1인 칸만 이동 대상으로 보면 된다.

---

6. 풀이 코드

from collections import deque

def solution(maps):
    n = len(maps)       # 행 개수
    m = len(maps[0])    # 열 개수

    # 상, 하, 좌, 우 이동 방향
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    # BFS를 위한 큐 생성
    q = deque()
    q.append((0, 0))  # 시작 위치

    while q:
        x, y = q.popleft()

        # 현재 위치에서 4방향 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 맵 범위를 벗어나면 제외
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            # 벽이거나 이미 방문한 칸이면 제외
            # 0: 벽
            # 1이 아닌 값: 이미 거리 값으로 갱신된 방문 칸
            if maps[nx][ny] != 1:
                continue

            # 다음 칸까지의 거리 저장
            maps[nx][ny] = maps[x][y] + 1

            # 다음 탐색 위치로 추가
            q.append((nx, ny))

    # 도착 지점 값이 1이면 도달하지 못한 것
    if maps[n - 1][m - 1] == 1:
        return -1

    # 도착 지점에 저장된 값이 최단 거리
    return maps[n - 1][m - 1]

 

6-1. 코드 추가 설명

이 코드에서 가장 중요한 부분은 다음이다.

maps[nx][ny] = maps[x][y] + 1

이 부분은 단순 방문 처리가 아니라:

현재 위치까지의 거리 + 1

을 다음 칸에 저장하는 역할이다.

예를 들어 현재 위치 값이 3이라면:

시작점에서 현재 칸까지 3칸 이동했다는 의미

이고,

다음 칸은:

3 + 1 = 4

가 된다.

즉, maps 배열 자체가:

• 이동 가능 여부 확인
• 방문 여부 확인
• 최단 거리 저장

세 가지 역할을 동시에 수행한다.

또 이 코드에서:

if maps[nx][ny] != 1:
    continue

 

조건도 중요하다.

처음 상태에서:

• 1 → 아직 방문하지 않은 이동 가능 칸
• 0 → 벽

이다.

그런데 방문하면:

maps[nx][ny] = maps[x][y] + 1

 

로 값이 바뀌기 때문에 더 이상 1이 아니다.

즉:

1이 아닌 값 = 이미 방문했거나 벽

 

이라는 의미가 된다.

그래서 별도의 visited 배열 없이도 방문 처리가 가능하다.

그리고 BFS에서 큐를 사용하는 이유도 중요하다.

q.popleft()

 

를 사용하면:

먼저 들어온 위치부터 탐색

 

하게 된다.

즉:

• 시작점에서 가까운 칸
• 그 다음 거리 칸
• 그 다음 거리 칸

순서로 탐색이 진행된다.

그래서 BFS는:

처음 도착한 경로가 곧 최단 거리

 

가 된다.

---

7. 핵심 로직 요약

이 문제의 핵심은 BFS로 가까운 칸부터 탐색하면서 거리 값을 누적하는 것이다.

• 시작점 (0, 0)을 큐에 넣는다.
• 큐에서 하나씩 꺼내 상하좌우를 확인한다.
• 범위를 벗어나거나 벽이면 제외한다.
• 아직 방문하지 않은 칸이면 현재 거리 + 1로 갱신한다.
• 도착 지점 값이 갱신되었다면 그 값이 최단 거리다.
• 도착하지 못했다면 -1을 반환한다.

결국, “큐 기반 BFS + 4방향 탐색 + 거리 누적” 이 흐름이 핵심이다.

---

8. 정리

처음 보면 단순히 길을 찾는 문제처럼 보이지만, 핵심은 “최단 거리”라는 조건이다.

이 조건 때문에 DFS보다 BFS가 더 자연스럽다.

특히 중요한 부분은 이거였다.

모든 이동 비용이 같으면 BFS가 최단 거리를 보장한다

 

또 별도의 visited 배열이나 distance 배열을 만들지 않고, 기존 maps에 거리 값을 직접 저장할 수 있다는 점도 중요했다.

결국 이 문제는 2차원 배열에서 BFS로 최단 거리를 구하는 기본 유형으로 정리할 수 있다.