[프로그래머스] 게임 맵 최단거리 (level2, python)

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

프로그래머스

아이디어

최단거리를 찾는 문제라서 bfs를 사용해서 풀었다.

    def bfs(x, y, N, M):
        nonlocal visited
        
        queue = deque([(x, y, 1)])
        
        while queue:
            x, y, l = queue.popleft()
            
            if x == N-1 and y == M-1: return l
            
            for dx, dy in dv:
                nx = x + dx
                ny = y + dy
                                
                if nx < 0 or nx >= N or ny < 0 or ny >= M or visited[nx][ny] == 1 or maps[nx][ny] == 0: 
                    continue
                
                visited[nx][ny] = 1
                queue.append((nx, ny, l+1))
        return -1

x, y 는 좌표 정보이고, l은 이동한 거리이다.

만약 큐만큼 돌았는데 리턴값이 없다면 -1을 리턴한다. (갈 수 없다는 뜻이므로)

 

구현할 때 visited 리스트를 처음에는 아래와 같이 선언하였는데,

visited = [[0] * M] * N

 

이렇게 선언하니 문제가 있었다.

파이썬 유저라면 눈치챘겠지만.. [[0]*M] 인 리스트를 N번 복제(얕은 복사)해서 넣는다.

즉 visited 리스트가 모두 같은 주소를 바라보게 된다.

만약 첫 번째 리스트를 [1, 0, 0]으로 수정했다면, 두번째도, 세번째도 모두 [1, 0, 0]이 되는 것이다.

 

그래서 list comprehension으로 다시 선언해주었다..

visited = [[ 0 for _ in range(M)] for _ in range(N)]

 

 

전체 코드

from collections import deque

def solution(maps):
    N = len(maps)
    M = len(maps[0])
    visited = [[ 0 for _ in range(M)] for _ in range(N)]
    
    dv = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    def bfs(x, y, N, M):
        nonlocal visited
        
        queue = deque([(x, y, 1)])
        
        while queue:
            x, y, l = queue.popleft()
            
            if x == N-1 and y == M-1: return l
            
            for dx, dy in dv:
                nx = x + dx
                ny = y + dy
                                
                if nx < 0 or nx >= N or ny < 0 or ny >= M or visited[nx][ny] == 1 or maps[nx][ny] == 0: 
                    continue
                
                visited[nx][ny] = 1
                queue.append((nx, ny, l+1))
        return -1
    
    return bfs(0, 0, N, M)