Programmers - 게임 맵 최단 거리 (Feat. Python)

[게임 맵 최단 거리]

프로그래머스

 

 

문제 설명

• n x m 크기의 맵에서 맵의 끝에 빨리 도착하는 방법 찾기
• (1,1) 에서 시작하며, 1회 이동에 한 칸씩 동, 서, 남, 북 네 방향으로 이동 가능
• 맵은 0과 1로 구성되어 있고, 0은 벽, 1은 이동할 수 있는 곳을 의미한다
• n과 m은 다를 수가 있고, n과 m이 모두 1인 경우는 존재하지 않는다
• 반환 값은 이동할 수 있는 최솟값을 반환하며, 맵의 끝에 도착하지 못 할 경우 -1을 반환한다

 

문제 접근

• 어떤 경로로 이동 하는지에 따라 최소 값이 달라질 수 있다
• 아래 사진처럼 이동하는 방법에 따라 여러 케이스가 나올 수 있다.

 

문제 해결 방법 - BFS 탐색

1. 첫 번째 경로부터 주변을 탐색하면서 마지막 좌표까지 이동한다.
2. 다음 경로로 이동할 수 있을 경우
   1. 해당 경로의 최솟값이 정해지지 않았다면 현재 경로까지의 최솟값을 더해준다
   2. 최솟값이 정해져 있다면, 해당 경로까지의 최솟값을 구한다.
3. 다음 경로로 이동할 수 없을 경우
   
   1. 맵을 벗어나는 경우
   2. 벽을 만나는 경우
   3. 시작 지점으로 돌아가는 경우
4. 마지막 위치 도달 가능 여부에 따라 -1 혹은 최솟값을 반환한다.

 

Code

def solution(matrix):
    n = len(matrix)
    m = len(matrix[0])
    
    # 하, 우, 좌, 상 이동
    dx = [1, 0, 0, -1] # 행
    dy = [0, 1, -1, 0] # 열

    # 현재 위치 저장
    q = []
    q.append((0,0))

    # 주변을 탐색하면서 마지막 좌표까지 이동 => BFS 탐색
    # 주변으로 이동할 수 없는 경우 => 결국 마지막 좌표에서 종료
    while len(q) > 0:
        pos = q.pop(0)

        # 하, 우, 좌, 상 이동
        for i in range(4):
            nx = pos[0] + dx[i]
            ny = pos[1] + dy[i]

            # 맵을 벗어날 경우
            if not (0 <= nx < n) or not (0 <= ny < m):
                continue
                
            # 시작 지점으로 돌아갈 경우
            if nx == 0 and ny == 0:
                continue

            # 벽을 만날 경우
            if matrix[nx][ny] == 0:
                continue

            # 가중치가 정해지지 않았을 경우
            if matrix[nx][ny] == 1:
                matrix[nx][ny] += matrix[pos[0]][pos[1]]
                
                # 다음 이동 위치를 q에 담는다
                q.append((nx, ny))
            # 가중치가 정해져있을 경우
            else:
                matrix[nx][ny] = min(matrix[nx][ny], matrix[pos[0]][pos[1]] + 1)
            				
    # 마지막 위치가 도달 불가능하면
    if matrix[n-1][m-1] == 1:
        return -1
    
    # 마지막 좌표의 가중치를 반환
    return matrix[n-1][m-1]