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

 

📌문제

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

 

🎖️난이도

Level 2

 

✔️풀이

from collections import deque

def solution(maps):
    dx = [0, 0, 1, -1] # 동서남북
    dy = [1, -1, 0, 0]
    
    #visited = [[0]*len(maps[0])]*len(maps) # error!!! (얕은 복사)
    visited = [[0]*len(maps[0]) for _ in range(len(maps))] # 최단거리 누적
    queue = deque([[0, 0]])
    visited[0][0] = 1
    
    # bfs
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]):
                if visited[nx][ny] == 0 and maps[nx][ny] == 1:
                    queue.append([nx, ny])
                    visited[nx][ny] += visited[x][y] + 1
                    
    answer = -1 if visited[-1][-1] == 0 else visited[-1][-1] # 3항 연산자
    
    return answer

 

🧠노트

최단거리(최단경로) & 모두 같은 거리(가중치) => BFS!

 

이 문제는 그냥 BFS의 기초였는데

맨 처음에 최단거리를 이동하면서 누적해가는 visited 2차원 배열 초기화를 잘못해서(얕은복사로ㅠ)

계속 왜 틀렸는지 모르고 애먹었다..

 

파이썬에서 2차원 리스트 초기화 시에는 리스트 내포와 for문을 이용하자!

 

🔍참고

[ 얕은 복사 vs 깊은 복사 ]

[Python] 얕은 복사🥵 vs 깊은 복사🤗

 

[ 3항 연산자 ]

[Python] 삼항 연산자 (3항 연산자)