게임 맵 최단거리 (python)

BFS with count 기본문제

👀 깃헙 소스

문제설명

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

입출력 예

maps		answer
[[1,0,1,1,1], 	11	
 [1,0,1,0,1],
 [1,0,1,1,1],
 [1,1,1,0,1],
 [0,0,0,0,1]]

솔루션
좌표값과 움직인 수를 같이 저장해두고 상하좌우 방향으로 BFS 탐색을 수행해준다.

코드

# 파이썬
from collections import deque

def visitable(N, M, y, x, maps):
    return 0 <= y < N and 0 <= x < M and maps[y][x] == 1

def solution(maps):
    
    N, M, Y, X, MOVE = len(maps), len(maps[0]), 0, 1, 2
    DELTAS = [(-1, 0), (1, 0), (0, 1), (0, -1)] # up down right left
    que, confirm = deque([(0, 0, 1)]), set((0, 0, 1))
    
    while que:
        cur = que.popleft()
        maps[cur[Y]][cur[X]] = 0
        
        if cur[Y] == N-1 and cur[X] == M-1:
            return cur[MOVE]            
        
        for dy, dx in DELTAS:
            next_p = (cur[Y] + dy, cur[X] + dx, cur[MOVE] + 1)
            if visitable(N, M, next_p[Y], next_p[X], maps) and next_p not in confirm:
                que.append(next_p)
                confirm.add(next_p)
        
    return -1

주의
첫칸도 카운트를 해야하므로 1로 셋팅해줘야한다.