[Programmers] level2 - 게임 맵 최단거리 (Python) : 깊이/너비 우선 탐색(DFS/BFS)

▶게임 맵 최단거리 - 깊이/너비 우선 탐색(DFS/BFS) (level 2)

▶문제          ▶제한사항          ▶출력

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

프로그래머스

이번에도 그림이 많은 문제여서 링크로 대체하겠습니다.

 

▶풀이

간단하게 dfs, bfs를 이용해서 풀면 되는 문제다.

deque를 이용해서 popleft를 하는 것은 bfs에 해당하는 풀이이다.

 

나는 bfs를 이용해서 문제를 풀었고, 방문한 적이 있는 곳을 기록하기 위해서 visited를 이용했다.

방문 유무만 판단하기 위함이 아니라, 몇 번 만에 그 칸에 도달했는지를 기록하기 위해서 사용했다.

그래서 마지막에 return 하는 것을 보면 -1 또는 visited [-1][-1]을 리턴하는 것을 볼 수 있다.

마지막 칸에 도달했을 때 그 숫자만 알면 되기 때문이다.

(visited [-1][-1]은 visited [len(maps) - 1][len(maps [0]) - 1]와 같습니다.)

from collections import deque


def solution(maps):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    visited = [[0 for _ in range(len(maps[0]))] for _ in range(len(maps))]
    visited[0][0] = 1
    
    queue = deque()
    queue.append([0, 0])
    
    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]) and maps[nx][ny] == 1:
                if visited[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append([nx, ny])
    
    if visited[len(maps) - 1][len(maps[0]) - 1] == 0:
        return -1
    return visited[len(maps) - 1][len(maps[0]) - 1]

정확성, 효율성 테스트 모두 통과해야 하는 문제이다.

bfs로 풀었을 때는 효율성까지 모두 통과되었다.

dfs는 아직 풀어보지 않아서 통과가 되는지 잘 모르겠다.