[프로그래머스/파이썬/JS] 게임 맵 최단걸이 풀이 (bfs, deque, python, deepcopy, JavaScript, 자바스크립트)

[프로그래머스/파이썬/자바스크립트] 게임 맵 최단거리 풀이

(JavaScript, JS, bfs, deque, Python, deepcopy)

 

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

---

2. 문제 해결 아이디어 (풀이)

 

1. 먼저 maps의 가로/세로 길이를 구한다.

 

2. 구하고자 하는 maps 배열을 복사한다. (깊은 복사)

 

3. BFS로 복사한 maps 배열을 탐색해서, 최단 경로를 구한다.

 

3.1. 탐색이 끝난 후에도 마지막 위치 노드가 '1'이라면 -> 벽으로 둘러싸여 있으므로 '-1'  반환

3.2. 탐색이 끝난 후에도 마지막 위치 노드가 '1'이 아니라면 -> 마지막 노드 값 반환 ( 최단거리가 된다) 

 

---

3. 코드 

Python

from collections import deque 
import copy

globalMaps = []

WALL = 0 # 벽
ROAD = 1 # 길

# 이동할 네 가지 방향 정의 (상,하,좌,우)
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(row, col, mapsRowLen, mapsColLen):
    global globalMaps
    # 큐 구현을 위해 deque 라이브러리 사용하기
    queue = deque()
    queue.append((row, col)) # 탐색할 x,y 구하기
    
    # 큐가 빌 때까지 반복하기
    while queue:
        row, col = queue.popleft()
        # 현재 위치에서 4가지 방향으로서 위치 확인 
        for i in range(4):
            nRow = row + dx[i]
            nCol = col + dy[i]

            # 맵 공간을 벗어난 경우 무시한다.
            if nRow < 0 or nRow >= mapsRowLen or nCol < 0 or nCol >= mapsColLen:
                continue
            # 벽인 경우에는 무시한다.
            if globalMaps[nRow][nCol] == WALL:
                continue
            
            # 해당 노드를 처음 방문했다면 최단 거리 기록 진행.
            if globalMaps[nRow][nCol] == ROAD:
                globalMaps[nRow][nCol] = globalMaps[row][col] + 1 # 기존 현 위치 + 새로 가게 될 위치 
                queue.append((nRow,nCol)) # 새 위치 큐에 기록

    # # # 다 돌았는데, 마지막 위치가 여전히 1이라면, -1 반환
    if globalMaps[mapsRowLen-1][mapsColLen-1] == ROAD:
        return -1
    else: # 가장 오른쪽 아래 도달했다면 아래 반환
        return globalMaps[mapsRowLen-1][mapsColLen-1]


def solution(maps):
    answer = 0
    global globalMaps
    
    # 1. n,m의길이를 구한다.
    mapsRowLen = len(maps)
    mapsColLen = len(maps[0])
    
    # 2. 구하고자 하는 map을 복사한다.
    globalMaps = copy.deepcopy(maps)
    
    # 3. bfs로 돌려서 최단 경로를 구한다. 
    answer = bfs(0, 0, mapsRowLen, mapsColLen)
    

    return answer

 

 

JavaScript

(2025.06.04 자바스크립트 코드 추가)

// 1. 글로벌한 함수 만들기 
let globalMaps = [];
const WALL = 0; // 벽
const ROAD = 1; // 길 

// 2. bfs 만들기 // row, col 시작 좌표, n, m 길이 
const bfs = (row, col, mapsRowLen, mapsColLen) => {
    // 상, 하, 좌, 우 좌표
    const dRow = [-1, 1, 0, 0];
    const dCol = [0, 0, -1, 1];
    let queue = [[row, col]]; // 시작 위치 저장

    while (queue.length > 0) { // js는 큐가 [] 비어있어도 True
        [row, col] = queue.shift() // 처음에서 x,y를 꺼낸다.
        
        // 현재 위치 기준 상,하,좌,우로 움직일 때, 길이 있는지 구한다.
        for (let i = 0; i < 4; i++) {
            let newRow = row + dRow[i];
            let newCol = col + dCol[i];
            
            // maps 영역을 벗어나면 해당 좌표는 무시.
            if (newRow < 0 || newRow >= mapsRowLen || newCol < 0 || newCol >= mapsColLen){
                continue;
            }
            
            // 벽이면 무시
            if (globalMaps[newRow][newCol] === WALL) {
                continue;
            }
            
            // 길 이면, 새 좌표를 큐에 추가하고 새 위치에도 값을 저장한다.
            if (globalMaps[newRow][newCol] === ROAD){
                queue.push([newRow, newCol]);
                globalMaps[newRow][newCol] = globalMaps[row][col] + 1;
            }
        }
        // 상,하,좌,우로 움직였을때 길이 있는지 구한다.
    }
    
    // 모든 경로 탐색이 끝났다면,
    // 마지막 도착 지점 값이 '1' 이라면 (길) -1 반환
    if (globalMaps[mapsRowLen-1][mapsColLen-1] === ROAD) {
        return -1;
    } else { // 아니면 방문한 값 반환
        return globalMaps[mapsRowLen-1][mapsColLen-1];
    }

}

function solution(maps) {
    var answer = 0;
    const mapsRowLen = maps.length;
    const mapsColLen = maps[0].length;
    
    globalMaps = maps;
    
    answer = bfs(0, 0, mapsRowLen, mapsColLen);
    
    
    return answer;
}

 

---

 

4. 코드 풀이 - BFS 코드

1. bfs 사용을 위한 큐 구현을 위해 deque 라이브러리를 사용한다.

def bfs(row, col, mapsRowLen, mapsColLen):
    global globalMaps
    # 큐 구현을 위해 deque 라이브러리 사용하기
    queue = deque()
    queue.append((row, col)) # 탐색할 x,y 구하기

 

- 이때 시작지점 row, col 값을 큐에 넣어준다.

 

2. 큐가 빌 때까지 bfs 반복을 진행한다.

    # 큐가 빌 때까지 반복하기
    while queue:
        row, col = queue.popleft()

 

- queue.popleft() 함수를 이용하여 제일 첫 번째 값을 빼주고, row, col 위치를 저장한다.

 

 

2.1 현재 위치에서 4가지 방향(상,하,좌,우)으로 방문 처리를 진행한다.

        # 현재 위치에서 4가지 방향으로서 위치 확인 
        for i in range(4):
            nRow = row + dx[i]
            nCol = col + dy[i]

            # 맵 공간을 벗어난 경우 무시한다.
            if nRow < 0 or nRow >= mapsRowLen or nCol < 0 or nCol >= mapsColLen:
                continue
            # 벽인 경우에는 무시한다.
            if globalMaps[nRow][nCol] == WALL:
                continue
            
            # 해당 노드를 처음 방문했다면 최단 거리 기록 진행.
            if globalMaps[nRow][nCol] == ROAD:
                globalMaps[nRow][nCol] = globalMaps[row][col] + 1 # 기존 현 위치 + 새로 가게 될 위치 
                queue.append((nRow,nCol)) # 새 위치 큐에 기록

 

- 첫 번째 if 문 :

맵 공간을 벗어난 경우(index = -1 )나, map의 가로/세로 길이(n,m)를 넘어가는 경우는 탐색하지 않도록 막아둔다

 

- 두 번재 if 문 :

현 위치가 벽인 경우(=0) 도 막아둔다

 

- 세 번재 if문 :

다음에 도착할 노드를 처음 방문하는 거라면 (=1) =>

  - 현재 노드의 거리 값 기준으로 다음 노드가 될 위치에 +1 해서 방문 처리를 해두고

  - queue에 새로 방문한 노드 위치를 추가해 준다.

 

** 참고로, BFS 과정을 출력해보면 , 아래와 같은 로직으로 진행된다. **

    

3. bfs를 다 돌았다면 [n, m] 번째 위치를 기준으로 알맞는 결과값을 리턴한다. 

    # # # 다 돌았는데, 마지막 위치가 여전히 1이라면, -1 반환
    if globalMaps[mapsRowLen-1][mapsColLen-1] == ROAD:
        return -1
    else: # 가장 오른쪽 아래 도달했다면 아래 반환
        return globalMaps[mapsRowLen-1][mapsColLen-1]

 

- 다 돌았는데 [n,m] 위치가 1이라면 -1 반환 진행

  => 즉 마지막 위치는 벽으로 둘러싸여 있기 때문에 경로 값이 업데이트되지 않았다는 뜻이다.

 

- 아니라면, [n, m] 번째 위치 값을 반환한다

  =>  [n,m] 번값이 즉 최단 경로가 된다!

 

 

---

4. 마무리

지난번에 한번 풀고 오랜만에 다시 한번 풀었다.

다시 풀어보니 bfs로 풀어야 하는 건 알겠는데 로직을 못 짜겠어서 결국 다시 보고 짰다.

 

그래도 지난번에는 풀이를 봐도 이해하는데 오래 걸렸는데, 

이번에는 전보다는 빨리 이해할 수 있었다!

 

반복이 진짜 중요한 것 같다