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

문제 설명

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

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

프로그래머스

 

문제 풀이

BFS로 문제를 풀이했습니다. 관련 개념이 아직 익숙하지 않아 관련 알고리즘 코드를 참고해서 작성했습니다.

현재 위치에서 동서남북 4방향을 모두 탐색하고, 이동 가능한 위치를 que에 저장하여 다시 탐색하는 방식으로 최단 거리를 찾습니다.

왜 이렇게 탐색하는게 최소값이 되는지가 헷갈려서 확인을 해봤는데요, 이유는 한번 지나간 칸은 다시 지나갈 수 없기 때문입니다.

돌아서 가는 길이 있다고 하더라도, 최단 경로에 이미 포함된 칸은 다시 지나갈 수 없기 때문에 긴 경로는 결과에 반영될 수 없는 것이죠.

그림으로 경로와 각 칸의 값이 변하는걸 확인해서 이해할 수 있었습니다ㅎㅎ

 

자세한 설명은 주석으로 달아두었습니다.

from collections import deque
def solution(maps):

    answer = bfs(0, 0, maps)
    
    # bfs 함수 return 값이 1 이라면 도달 불가능을 의미하므로 -1 return
    return -1 if answer == 1 else answer

def bfs(x, y, maps):
	# 4방향(동서남북)
    dir_x = [-1, 1, 0, 0]
    dir_y = [0, 0, -1, 1]
    
    queue = deque()
    queue.append((x, y))
    
    # queue에 값이 없을 때까지 반복
    while queue:
        x, y = queue.popleft()
        
        # 4방향으로 진행
        for i in range(4):
            curx = x + dir_x[i]
            cury = y + dir_y[i]
            
            # map 범위를 벗어나면 계속 진행 X
            if curx < 0 or curx >= len(maps) or cury < 0 or cury >= len(maps[0]): continue
            # 이동 위치가 벽인 경우 진행 X
            if maps[curx][cury] == 0: continue
            # 이동 가능한 위치인 경우, queue에 현재 위치 추가 & 지금까지 이동한 거리 체크
            if maps[curx][cury] == 1:
                maps[curx][cury] = maps[x][y] + 1
                queue.append((curx, cury))
                
    # 마지막 도착 위치(우하단)에 저장 된 거리 return
    return maps[len(maps)-1][len(maps[0])-1]