[프로그래머스] Lv2. 게임 맵 최단거리(Python)

문제 링크

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

풀이 시간

약 26분

접근 방식

최단거리 = BFS로 풀어야 겠다는 생각을 먼저 했다.

시작점인 (0,0) 과 시작할때 방문한 칸의 개수는 1이기 때문에, 큐에 [0,0,1] 형태로 배열을 넣어줬다.

현재 좌표와 인접한(상하좌우) 칸을 비교하며 방문가능하고, 비어있는 칸이면 큐에 넣어준다. 이때 큐에 넣어줄때 방문한 칸의 개수를 1 늘려서(cnt+1) 넣어줘야 한다.

큐에서 값을 뽑아 확인하다가 (n-1,m-1)에 도달하면, 현재까지 방문한 칸의 개수인 cnt를 리턴해준다.

만약 큐를 다 순회했는데도 (n-1,m-1)에 도달하지 못했다면, 이는 상대팀 진영에 도착하지 못하는 경우가 되므로 -1을 리턴해준다.

정답 코드

from collections import deque
def solution(maps):
    n, m = len(maps), len(maps[0])
    answer = 0
    visited = [[False] * m for _ in range(n)]
    
    queue = deque()
    queue.append([0,0,1])
    visited[0][0] = True
    
    dir = [[-1,0], [0,1], [1,0], [0,-1]]

    while queue:
        [x,y,cnt] = queue.popleft()
        if x==n-1 and y==m-1:
            return cnt
        for d in dir:
            nx = x+d[0]
            ny = y+d[1]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if not visited[nx][ny] and maps[nx][ny] == 1:
                queue.append([nx,ny,cnt+1])
                visited[nx][ny] = True
    
    return -1

Thinking 👀

처음 코드를 작성할때 효율성테스트에서 시간초과가 떠서 어느부분에서 시간이 오래걸리는거지..? 하고 queue 값을 출력해봤더니 visited 리스트를 True로 방문처리해주는 코드의 위치가 문제였다.

수정전 코드에서는 visited 방문처리를 큐에서 값을 뽑고나서 했었는데, 이렇게하면 같은 좌표의 값이 중복해서 큐에 들어갈수 있게 된다. 이미 큐에 넣은 값을 다시 큐에 넣지 않도록 큐에 값을 넣음과 동시에 visited 방문처리를 해줬더니 효율성 테스트도 통과했다.