[DFS/BFS] 게임 맵 최단거리(프로그래머스, Level2)

문제

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

• 게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

풀이

BFS 알고리즘으로 풀이하였다. 상, 하, 좌, 우로 이동할 때의 좌표 변화 값을 dx, dy 배열을 활용해 각각 저장한 후, 사용자의 좌표를 움직여보면서 이동 가능할 때 이동을 진행한다.
maps 배열에 사용자가 한 칸씩 이동할 때마다 배열 값을 1씩 증가하여 기록하면서 최종적으로 도착 지점에 도착했을 때의 이동 횟수를 정답으로 리턴한다.
만약 최종 목적지에 도달하지 못한다면 -1을 리턴한다.

코드

from collections import deque
def solution(maps):
    answer = 0
    
    n, m = len(maps), len(maps[0])
    visited = [[0]*m for _ in range(n)]
    
    answer = bfs(maps, visited, 0, 0)
    
    return answer

def bfs(maps, visited, x, y):
    n, m = len(maps), len(maps[0])
    
    dx = [0, 0, -1, 1]  # 상하좌우
    dy = [-1, 1, 0, 0]

    queue = deque()
    queue.append((x, y))
    visited[x][y] = 1
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx >= 0 and nx < n and ny >= 0 and ny < m:
                if maps[nx][ny] == 1 and visited[nx][ny] == 0:
                    maps[nx][ny] = maps[x][y]+1
                    queue.append((nx, ny))
                    visited[nx][ny] = 1
    
    if maps[n-1][m-1] == 1:
        return -1
    else:
        return maps[n-1][m-1]

결과 실행 화면