프로그래머스 LV1 게임 맵 최단 거리

 

문제

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

프로그래머스

 

 

 

풀이

해당 문제는 Baekjoon에서 많이 풀어본 문제라 정형적인 풀이 방식으로 접근해 문제를 풀었다. DFS, BFS 방식이 있지만, 최단거리와 미로 관련 문제는 BFS로 풀면 쉽게 풀리는 데이터가 머리에 남아 있어서 해당 문제 또한 BFS 방식으로 풀었다. 

 

풀이 방법은 다음과 같다.

• x, y 좌표에서 상하좌우를 비교하여 조건에 충족했을 때, queue에 x, y을 추가한다.
• maps [nx][ny]의 값은 maps [x][y] + 1 값을 추가하여 작성한다. 

 

해당 값을 누적하여 문제를 풀어 나간다면, 그림은 이렇게 그려진다. 

 

 

🖥️ main.py

from collections import deque


def solution(maps):
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    
    def bfs(x, y):
        queue = deque()
        queue.append((x, y))
        
        while queue:
            x, y = queue.popleft()
            
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
            
                if nx < 0 or nx >= len(maps) or ny < 0 or ny >= len(maps[0]):
                    continue
                elif maps[nx][ny] == 0:
                    continue
                elif maps[nx][ny] == 1:
                    maps[nx][ny] = maps[x][y] + 1
                    queue.append((nx, ny))
        
        return maps[len(maps)-1][len(maps[0])-1]
    
    answer = bfs(0, 0)
    return -1 if answer == 1 else answer