[DFS] 게임 맵 최단거리 - level2

[heerucan]

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

문제 설명

• 미로탐색이랑 똑같음
• 그래프 내에서 최단거리 구하는 문제이고, 1이 있으면 이동이 가능하고, 0이 있으면 이동 못함 -> BFS
• n, m인 끝까지 갈 수 있어야 성공! 갈 수 없으면 -1을 반환해야 함

from collections import deque
    
def solution(maps):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    n = len(maps)
    m = len(maps[0])

    def bfs(x, y):
        queue = deque()
        queue.append((x,y))
        
        while queue:
            x, y = queue.popleft()
            
            for i in range(4):
                xx = x + dx[i]
                yy = y + dy[i]
                
                if xx < 0 or xx >= n or yy < 0 or yy >= m:
                    continue

                if maps[xx][yy] == 0:
                    continue
                
                if maps[xx][yy] == 1:
                    maps[xx][yy] = maps[x][y] + 1
                    queue.append((xx, yy))

        if maps[n-1][m-1] == 1:
            return -1
        else:
            return maps[n-1][m-1]

    return bfs(0,0)

문제 풀이

• 중간에 벽이 있어서 n,m까지 가지 않으면 bfs 돌리면 1이 나옴 그래서 그럴 때 -1을 줌