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

찾아라 프로그래밍 마에스터 문제

문제 풀러 바로가기 👇👇👇👇👇👇

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

코딩테스트 연습 - 게임 맵 최단거리

 

 

문제내용은 위 링크 참고바람

 

 

문제풀이

---

위 문제는 BFS(너비 우선 탐색)을 이용하면 아주 쉽게 풀 수 있는 문제이다. queue(deque 라이브러리 사용)를 이용해 지도의 좌표를 저장하고 차례대로 좌표를 꺼내 퍼트려나가면 된다. 방향은 위, 아래, 왼쪽, 오른쪽 총 4가지로 현재좌표에 방향을 적용했을 때 그 값이 유효하다면 현재좌표+1 값을 방향을 적용한 좌표에 넣어 현재 몇 칸을 거쳐왔는지 표시해주면 된다. 마지막으로 유효한 좌표를 queue에 삽입해준다.

 

퍼져나가는 도중에 나아갈 방향의 좌표에 해당하는 값이 1보다 크다면 이미 방문한 좌표이기 때문에 continue를 통해 무시해주면 된다. (이 논리를 적용해야 최단거리를 구할 수 있음)

 

마지막 리턴할 때 목표 좌표(n-1, m-1)를 리턴해주면 된다. 여기서 유의할 점은 목표지에 도달하지 못했을 때 -1을 리턴하는 것인데, 목표지의 값이 0이거나 1이면 도달하지 못한 것이므로 이 때 -1을 반환해주면 된다.

 

 

 

 

코드

---

def solution(maps):
    from collections import deque
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    n = len(maps)
    m = len(maps[0])

    queue = deque()
    queue.append((0, 0))

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue

            if maps[nx][ny] > 1 or maps[nx][ny] == 0:
                continue

            if nx == 0 and ny == 0:
                continue

            queue.append((nx, ny))
            maps[nx][ny] += maps[x][y]

    return maps[n-1][m-1] if maps[n-1][m-1] > 1 else -1