코딩테스트 게임 맵 최단거리 문제풀이

프로그래머스 게임 맵 최단거리(level 2) 문제풀이

from collections import deque

def solution(maps):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    queue = deque()
    x, y = 0, 0
    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 ny<0 or nx>=len(maps) or ny>=len(maps[0]):
                continue
            if maps[nx][ny] == 0:
                continue
            if maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y]+1
                queue.append((nx, ny))
    if maps[len(maps)-1][len(maps[0])-1] == 1:
        return -1
    else:
        return maps[len(maps)-1][len(maps[0])-1]

BFS알고리즘을 사용했는데 처음에 캐릭터 인덱스를 큐에 넣고 상하좌우를 확인하면 한번도 안가본 곳(값 = 1)일 경우 이전 값을 더해준다.
그렇게 모든 인덱스의 값을 갱신시킨다

그리고 마지막에 상대방 진영의 값이 1인 경우는 못갔을 경우이기 때문에 -1을 리턴해준다. 아닐경우는 그 인덱스 값을 리턴한다