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

 

가장 먼저 해야 할것은 어떤 알고리즘, 자료구조를 사용할지 파악을 하는 것이다.

1. 문제 유형 파악

• 맵을 통한 경로 탐색 : 2차원 격자 맵에서 목표 지점까지의 경로를 찾는 문제이다.
• 최단 경로 요구 : 문제는 "최단 경로"를 찾는것을 요구한다.

2. 그래프 탐색 문제 인식

• 격자 맵 : 격자 맵에서 각 칸은 노드, 이동은 간선으로 볼 수 있다. 즉, 이 문제는 그래프 탐색 문제로 바라볼 수 있다.
• 무가중치 그래프 : 각 이동은 동일한 비용(칸을 한 칸 이동하는 비율은 동일)이다. 가중치가 없는 그래프로 볼 수 있다.

3. 최단 경로 탐색 요구

• 최단 경로 보장 :  문제에서의 요구 사항은 목적지 까지의 최단 경로를 찾는 것이다.
• 무가중치 그래프의 최단 경로 : 무가중치 그래프에서 최단 경로를 찾기 위한 가장 효율적인 알고리즘은 BFS이다. BFS는 먼저 방문한 경로가 최단 경로임을 보장한다.

아래는 제출해 통과한 코드이다.

from collections import deque

def solution(maps):
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    n = len(maps)
    m = len(maps[0])
    
    queue = deque([(0,0,1)])
    visited = [[False] * m for _ in range(n)]
    visited[0][0] = True
    
    while queue:
        x, y, distance = queue.popleft()
        
        if x == n - 1 and y == m - 1:
            return distance
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1 and not visited[nx][ny]:
                queue.append((nx, ny, distance + 1))
                visited[nx][ny] = True
    return -1

 

- BFS는 큐를 사용해 인접한 모든 노드를 방문하는 방식이다. 큐를 사용하기 위해 from collections import deque를 해 준다.

 

- 다음으로, 한 노드(격자에서는 현재 서있는 위치)에서 한칸씩 갈 수 있는 모든 방향을 담은 directions 배열을 선언하고 초기화 한다.

동, 서 , 남, 북 으로 총 4가지의 경우가 있으므로 (1, 0)[동] // (-1, 0)[서] // (0, 1)[남] // (0, -1)[북] 과 같이 지정 해준다.

 

- 또한, 입력값으로 주어진 maps의 크기를 구하기 위해 행, 열의 길이를 각각 n, m에 매핑 시켜준다.

 

- 다음으로 , 큐를 선언해주고 [0, 0, 1]의 값을 비어있는 큐에 넣어준다. 여기서는 (x, y, distance)인데, 즉 맨 처음의 좌표는 (0,0)이고, 여기서는 시작 지점 자체도 포함한 이동 칸의 수를 계산해야 하므로 초기 거리를 1로 설정한다.

 

- 다음으로, 방문 여부를 확인하는 2차원 배열 visited를 선언 해준다. 이 2차원 배열의 초기 상태는 n * m 만큼의 2차원 배열에 False로 채워넣어 아직 방문하지 않았다는걸 의미한다.

 

- 첫번째 시작점은 이미 방문했으므로 visited[0][0] = True로 설정한다.

 

- 이제, 위에서 선언한 큐에 요소가 없을때까지 다음 while문을 반복한다.

 

- 큐에서 요소 하나를 꺼낸다. 요소를 꺼내어 각각 x, y, distance에 할당한다.

 

- 만약, 이미 끝 지점에 도달했다면(if x == n - 1 and y == m - 1) 현재까지 저장된 거리를 리턴하고 끝낸다.

 

- 아직 끝에 도달하지 않았다면, 위에서 선언한 동 서 남 북의 값이 담긴 directions 배열을 순회한다.

 

- 예를 들어보자. 현재 큐에 있는 값은 (0,0,1)이고, 이 0, 0, 1은 각각 x, y distance에 매핑된다. 아직 현재 값은 끝에 도달하지 않았으므로 첫번째 if문은 통과되고, 다음으로 directions에 있는 동쪽 값(1, 0)을 꺼내 현재 위치에서(0, 0, 1) 동쪽으로 한칸 이동한다. 이렇게 되면 nx, ny에는 1, 0이 담길 것이다.

 

- 다음으로, 이렇게 업데이트 된 값을 가지고 유효성을 검사한다. 여기서의 유효성이란, maps의 범위를 벗어나지 않았는지, 즉, 처음 입력값으로 주어진 n x m 격자 배열의 범위에서 벗어나지 않는지(if 0 <= nx < n and 0 <= ny < m), 또 문제에서 1은 갈 수 있는 노드, 0은 갈 수 없는 막힌 노드로 설정이 되어 있으므로, 가려는 칸이 1인지(갈 수 있는 노드인지) 판별을 해야한다.(and maps[nx][ny] == 1) 또한, 이미 방문한 노드라면 다시 방문하지 않아도 되므로 not visited[nx][ny]를 통해 방문한적 있는지 없는지를 검사한다.

 

-예를 들어보자. 위의 예시에서의 입력값을 기준으로 동쪽으로 가려고 한다면 and maps[nx][ny] == 1 여기서 False를 반환할것이다. 다음은 현재 노드의 서쪽을 검사하는데, 서쪽은 maps의 범위를 벗어나므로 여기서도 false를 반환 할 것이다. 다음으로, 남쪽을 검사할땐, 남쪽은 현재 maps의 범위를 벗어나지 않고, 노드의 값은 1이고, 아직 방문한적이 없으므로 큐에 업데이트 된 값을 넣어준다. 여기서는 

queue.append(nx, ny, distance + 1)를 하여 현재 이동한 노드의 좌표와 현재까지 이동한 거리를 넣어준다. 이 문제에서는 한번에 한 칸씩 이동하므로 distance + 1을 해주면 된다. 또한 이 노드는 이제 방문한 노드가 되므로 visited또한 True로 해줘야 한다.

 

 

여기서 궁금한 점이 생겼다. 로직 자체는 현재 검사중인 노드에서 동 서 남 북의 위치를 각각 검사하여 갈 수 있다면 그 노드를 큐에 넣고 같은 작업을 반복하는데, 이게 어떻게 최단 거리를 도출 할 수 있지?

 

다음은 GPT에게서 얻어낸 답변이다!

이 과정을 계속 반복하면, 최단 경로로 목표 지점 (4, 4)에 도달하게 됩니다. BFS는 현재 위치에서 가능한 모든 경로를 탐색하기 때문에, 먼저 도달한 경로가 최단 경로임을 보장합니다.

from collections import deque

def solution(maps):
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    n, m = len(maps), len(maps[0])
    queue = deque([(0, 0, 1)])
    visited = [[False] * m for _ in range(n)]
    visited[0][0] = True

    while queue:
        x, y, distance = queue.popleft()
        if x == n - 1 and y == m - 1:
            return distance
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1 and not visited[nx][ny]:
                queue.append((nx, ny, distance + 1))
                visited[nx][ny] = True

    return -1

# 예시 테스트
maps1 = [[1,0,1,1,1], [1,0,1,0,1], [1,0,1,1,1], [1,1,1,0,1], [0,0,0,0,1]]
maps2 = [[1,0,1,1,1], [1,0,1,0,1], [1,0,1,1,1], [1,1,1,0,0], [0,0,0,0,1]]
print(solution(maps1))  # 출력: 11
print(solution(maps2))  # 출력: -1