[프로그래머스] 게임 맵 최단거리(Lv.2) - 파이썬(Python)

문제

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

프로그래머스

 

풀이

이 코드는 주어진 maps 에서 BFS(너비 우선 탐색)을 사용하여 출발점 (0, 0)에서 도착점 (m-1, n-1) 까지의 최단 경로를 찾아내는 문제를 해결하는 코드입니다.

각 칸에서 갈 수 있는 경로는 1로 표시되며, 0은 벽으로 갈 수 없는 경로를 나타냅니다.

 

1. 변수 설명 및 초기 설정

m = len(maps)       # 행의 수
n = len(maps[0])    # 열의 수

• m 은 맵의 행(row) 수를 나타내며, n은 열(column) 수를 나타냅니다. 즉, 맵은 m x n 크기입니다.

visited = [[False]*n for _ in range(m)]

• visited는 방문 여부를 기록하는 2차원 리스트입니다.

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

• dx 와 dy 는 상하좌우 이동을 위한 방향입니다. 이 값들을 이용해 각각 위, 아래, 좌, 우로 이동할 수 있습니다.

 

2. BFS 함수 설명

def bfs(x, y):
    q = deque()
    q.append([x, y])
    visited[x][y] = True

• bfs 함수는 (x, y) 좌표에서 BFS 탐색을 시작합니다.
• deque는 큐 자료구조로, BFS를 수행하기에 적합합니다. 첫 시작점 (0, 0)을 큐에 넣고 visited 를 true로 설정합니다.

while q:
    xx, yy = q.popleft()

• 큐가 비어 있지 않은 동안 BFS를 수행합니다. q.popleft() 는 큐에서 가장 먼저 들어간 좌표를 꺼냅니다.

for i in range(4):
    nx = xx + dx[i]
    ny = yy + dy[i]

• 상하좌우로 이동하기 위해 dx, dy 방향을 사용해 좌표 (nx, ny)를 계산합니다.

if 0 <= nx < m and 0 <= ny < n:
    if maps[nx][ny] != 0 and not visited[nx][ny]:
        visited[nx][ny] = True
        maps[nx][ny] = maps[xx][yy] + 1
        q.append([nx, ny])

• 새로운 좌표 (ny, nx)가 맵의 범위를 벗어나지 않고 (0 <= nx < m and 0 <= ny < n), 벽이 아닌 곳(maps[nx][ny] != 0) 이며 아직 방문하지 않은 곳 ( not visited[nx][ny] ) 인 경우에만 이동합니다.
• 이동할 수 있으면 visited[nx][ny] = True로 방문 여부를 기록하고, 그 위치의 값을 현재 위치 maps[xx][yy]에 1을 더한 값으로 갱신합니다. 이는 BFS 특성상 최단 경로임을 보장합니다.
• 이후 (nx, ny) 좌표를 큐에 추가하여 계속 탐색합니다.

 

3. 최종 결과 계산

if maps[m-1][n-1] == 1 or maps[m-1][n-1] == 0:
    answer = -1
else:
    answer = maps[m-1][n-1]

 

• BFS 탐색이 끝난 후 도착점 (m-1, n-1)의 값이 1이거나 0이면, 이는 경로가 없음을 의미하므로 answer = -1로 설정합니다. 1은 도착점이 초기 상태인 경우이며, 0은 도착할 수 없는 경우입니다.
• 도착점의 값이 1보다 크면, 이는 시작점에서 도착점까지의 최단 경로의 길이를 나타내므로, 그 값을 answer에 저장합니다.

 

 

최종 코드

from collections import deque

def solution(maps):
    
    answer = 0
    m = len(maps)       # 행의 수
    n = len(maps[0])    # 열의 수 
    
    visited = [[False]*n for _ in range(m)]
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    def bfs(x, y):
        q = deque()
        q.append([x,y])
        visited[x][y] = True
        
        while q:
            xx, yy = q.popleft()
            
            for i in range(4):
                nx = xx+dx[i]
                ny = yy+dy[i]
                
                if 0<= nx < m and 0 <= ny < n:
                    if maps[nx][ny] != 0 and not visited[nx][ny]:
                        visited[nx][ny] = True
                        maps[nx][ny] = maps[xx][yy] + 1
                        q.append([nx, ny])
        
    bfs(0,0)
    
    
    if maps[m-1][n-1] == 1 or maps[m-1][n-1] == 0:
        answer = -1
    else:
        answer = maps[m-1][n-1]
        
    return answer