[프로그래머스/파이썬] 게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

까다로운 조건이 없는 BFS 문제이다

 

한가지 팁은, 아래의 cnt 변수를 어떻게 잘 조작하면 굳이 방문 배열을 사용하지 않고도 풀 수 있다는 점을 잘 생각해보시길..

from collections import deque

def solution(maps):
    answer = -1
    
    dq = deque()
    dq.append([[0,0],1])

    end_x, end_y = len(maps), len(maps[0])
    
    dx = [0,1,-1,0]
    dy = [1,0,0,-1]
    
    visited = [[False for _ in range(end_y)] for _ in range(end_x)]
    visited[0][0] = True
    while dq:
        now, cnt = dq.popleft()
        x = now[0]
        y = now[1]
        #print(x,y)
        if x == end_x-1 and y == end_y-1:
            answer = cnt
            break
            
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= end_x or ny < 0 or ny >= end_y:
                continue
            if visited[nx][ny] or maps[nx][ny]==0:
                continue
                
            visited[nx][ny] = True
            dq.append([[nx,ny],cnt+1])
        
    return answer