[bfs / 프로그래머스] 1844번 : 게임 맵 최단거리

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

 

Lv2 문제이고, 스스로 푼 문제다!

기본 탐색 문제이고, 탐색하면서 (0,0) 에서 (-1, -1)까지 가는 경로 중 최단거리를 반환하는 문제다 

 

문제 풀이

- 지나왔던 길 다시 가면 안되니까 visit 처리해주고, 벽인 곳(0) 지나가면 안되니까 0이 아닌 곳일 때 진입할 수 있다.

- 최단 거리를 의미하므로 만약 가는 길이 초행길이라면 현재 위치의 값을 더해주면 되고 다른 길이 지나갔는데 현재 길에서 가는게 더 최단거리라면 기존에 있는 값과 현재 위치 값 + 1을 비교해서 최솟값을 누적해준다.

- 방문 처리와 이동까지 처리해준다

- 오른쪽 끝이 1이라면 주변이 벽으로 막힌 경우이므로 -1을 반환하고, 아니라면 해당 위치의 값을 반환한다 

 

- 정답 풀이 : 

from collections import deque

def solution(maps):
    n = len(maps)
    m = len(maps[0])
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    queue = deque()
    queue.append((0,0))
    visit = [[0] * m for _ in range(n)]
    visit[0][0] = 1

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