[알고리즘] 프로그래머스 게임 맵 최단 거리 파이썬

[프로그래머스] LEVEL2 게임 맵 최단 거리

✅ 문제

✅ 나의 풀이

'이코테' 강의의 미로문제와 유사했기 때문에 BFS 알고리즘을 사용해야겠다는 생각은 들었으나 처음부터 끝까지 완벽하게 구현해내지는 못했다. 많이 연습해야겠다.

• BFS 알고리즘 + 큐 자료구조 이용
• maps 배열에 최단 거리를 적어주는 방식

from collections import deque
def solution(maps):
    answer = 0
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    w = len(maps[0])
    h = len(maps)
    
    queue = deque()
    queue.append((0, 0))
    while queue :
        x, y = queue.popleft()
        if x == (h-1) and y == (w-1) :
            answer = maps[x][y]
            break
        for i in range(4) :
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= h or ny >= w :
                continue
            if maps[nx][ny] != 1 :
                continue
            queue.append((nx, ny))
            maps[nx][ny] = maps[x][y] + 1
    else :
        answer = -1
    return answer

첫 구현에서는 아래와 같이 무한루프를 돌리고 break하는 방식을 선택했다. 하지만 무한루프가 불안했고, 예외 처리 if문의 순서를 맞히는 것도 쉽지 않았고 코드도 깔끔하지 않아서 위와 같이 변경했다. 저번 문제를 통해 알게 된 while-else 구문을 사용했다는 것이 뿌듯하다.

while True :
	if not queue :
		answer = -1
		break

코드를 작성하며 가장 헤맸던 부분은 게임 맵의 width와 height를 찾는 부분이었다.
아래와 같이 2차원 slicing을 적용하면 되겠다고 생각했으나,

width = len(maps[0][:])
height = len(maps[:][0])

위 두 배열은 같은 배열(첫번째 행)을 의미해서 항상 같은 값이 출력되었다. 이는 아래와 같이 변경했다.

width = len(maps[0])
height = len(maps)

✅ 얻어가기

• BFS. 반복문과 큐 사용하기.
• DFS. 재귀 함수 또는 스택 사용하기.

• 무한 루프 사용 대신 while-else 구문 사용
• 2차원 slicing은 불가능하다는 사실