📚 1844 - 게임 맵 최단거리

게임 맵 최단거리

이해

문제를 보면 (0, 0) 위치에서 (마지막 행, 마지막 열)로 간다.
움직일 수 있는 방향은 동서남북이다.
또한, 한번 지나간 경로는 다시 지나갈 수 없다.

벽이 있는 자리 0
벽이 없는 자리 1

이와 같아 벽이 없는 자리 1를 지나갈 때 0으로 바꿔주면 그자리는 벽이 있는 자리가 되므로, 이미 지나간 경로라는 것을 알 수 있다.

전형적인 bfs문제이다.

소스

from collections import deque

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

def dfs(col, row, maps):
    queue = deque()
    queue.append((0, 0, 1))
    res = 1e9
    
    while queue:
        x, y, cnt = queue.popleft()
        
        if x == row - 1 and y == col - 1:
            if res > cnt:
                res = cnt
        else:
            for i in range(4):
                next_x = x + dx[i]
                next_y = y + dy[i]
                
                if 0 <= next_x < row and 0<= next_y < col:
                    if maps[next_x][next_y] == 1:
                        maps[next_x][next_y] = 0
                        queue.append((next_x, next_y, cnt + 1))
    
    if res == 1e9:
        res = -1
    
    return res
    

def solution(maps):
    answer = 0
    col = len(maps[0])
    row = len(maps)
    
    if maps[0][0] == 0:
        answer = -1
    else:
        answer = dfs(col, row, maps)
    
    return answer