99클럽 TIL (240825)

> [Middler] 게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=python3#

 

문제 풀이 과정

캐릭터는 1,1 좌표에서 시작하고 상대팀 진영은 맨 우측 하단에 위치해있다. 최단거리를 구하면 되기 때문에 BFS를 사용했다.

 

문제 풀이

from collections import deque
def solution(maps):
    dist = [[0] * len(maps[0]) for _ in range(len(maps))]
    d = [(0,-1),(0,1),(-1,0),(1,0)]
    
    dist[0][0] = 1
    
    q = deque()
    q.append((0,0))
    while q :
        x, y = q.popleft()
        
        if x == len(maps)-1 and y == len(maps[0])-1 :
            break
        
        for i in range(4) :
            nx = x + d[i][0]
            ny = y + d[i][1]
            if nx < 0 or ny < 0 or nx >= len(maps) or ny >= len(maps[0]) : continue
            if maps[nx][ny] == 0 or dist[nx][ny] != 0 : continue
            
            q.append((nx,ny))
            dist[nx][ny] = dist[x][y] + 1
            
    if dist[len(maps)-1][len(maps[0])-1] != 0 :
        return dist[len(maps)-1][len(maps[0])-1]
    else :
        return -1