[프로그래머스LV2] 게임 맵 최단거리

[LV2] 게임 맵 최단거리 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. www.programmers.co.kr

 

문제해설

이번문제는 최단거리를 구하는 문제이며 이런 문제의 경우가 대표적인 BFS 문제라고 볼 수 있다. bfs로 풀기 위해서는 각각의 위치를 좌표화 하여 움직일 수 있는부분의 시작지점에서 부터의 거리를 현재 위치 거리의 +1을 해주면 풀 수 있고 deque를 사용하여 현재 움직일 수 있는 위치를 확인하면 된다.

from collections import deque

def solution(maps):
    answer = 0
    n=len(maps) #맵의 세로길이 확인 
    m=len(maps[0]) #맵의 가로길이 확인  
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    graph=[[-1]*m for _ in range(n)] #각 위치의 최단거리를 확인하기 위해 맵 생성
    que=deque()
    que.append((0,0)) #시작위치 삽입 
    while que: # bfs 사용
        x,y=que.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if graph[nx][ny]==-1 and maps[nx][ny] ==1:
                    graph[nx][ny]=graph[x][y]+1
                    que.append((nx,ny))
    if graph[n-1][m-1] == -1 : #모든 위치의 시작을 -1로 잡았기 때문에 도착하지 못하는 경우 외에는 +2
        return -1 
    else:
        return graph[n-1][m-1]+2