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

Source

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

프로그래머스

 

Code

from collections import deque

def solution(maps):
    n, m = len(maps), len(maps[0])
    # 1. BFS를 실행할 아웃라인을 정해 준다. ( n = x값의 최대치, m = y 값의 최대치 )
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    # 2. 로봇이 움직일 상하 좌우를 정해 준다.
    queue = deque([(0, 0, 1)])
    # 3. 처음 지점을 큐에 넣어 준다.

    while queue:
        # 4. 큐에 값이 있을 때를 기준으로 while문 작성

        x, y, cnt = queue.popleft()
        # 5. 큐에서 하나의 지점을 꺼냄

        if x == n-1 and y == m-1:
            # 6. 상대 팀 진영에 도착한 경우 cnt 반환
            return cnt

        for i in range(4):
            # 7. 상하 좌우 탐색
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1:
                # 8. 이동 가능 여부 체크
                queue.append((nx, ny, cnt+1))
                # 9. 이동 가능한 위치를 큐에 추가
                maps[nx][ny] = 0
                # 10. 현재 위치를 방문한 것으로 표시

    return -1
    # 11. 모두 실행 해도 상대 팀 진영에 도착 못한 경우 -1 리턴

 

How to solve?

해당 문제는 '최단거리' 파악 문제이기 때문에 BFS를 이용해서 해결한다.

BFS는 거리가 1인 노드를 전부 파악한 뒤 거리가 2인 노드를 파악하고 그다음 3, 4와 같이

거리의 순서대로 노드를 파악하기 때문에 최단거리 경로이다.

출처: https://nulls.co.kr/graph/141

 

1. BFS를 실행할 아웃라인을 정해준다.

n은 x값의 최대치이며 m은 y값의 최대치이다.

문제에서 주어진대로 생각하면 n은 y값의 최대치이고, m은 x값의 최대치여야 하지만,

로봇이 있는 자리를 (0.0)으로 생각하고 도착 지점을 (4.4)로 생각해서 x와 y를 바꿔준다.

 

2. 로봇이 움직일 상하좌우를 정해준다.

 

3. 처음 지점을 큐에 넣어준다.

 

4. 큐에 값이 있을 때를 기준으로 while문을 작성한다.

이 while문이 반복되며 BFS를 실행한다.

 

5. 큐에서 하나의 지점을 꺼내준다.

 

6. 만약 꺼낸 지점의 x, y가 도착지하면 cnt를 리턴하며 끝낸다.

 

7. 상하 좌우를 탐색해준다.

 

8. 탐색한 이동 방향이 이동 가능한지 여부를 체크한 뒤

 

9. 이동이 가능하다면 그 위치를 큐에 추가 해준다.

 

10. 현재 위치를 방문한 것으로 표시 해준다.

 

11. 위의 절차를 전부 수행 해도 상대 진영에 도착하지 못한다면 -1을 리턴 해준다.