[Programmers] 게임 맵 최단거리 (DFS/BFS Lv.2) - Python

1. 문제

---

게임 맵 최단거리

2. 풀이

---

코드

from collections import deque

def bfs(start_x, start_y, maps):
    rows = len(maps)
    cols = len(maps[0])
    queue = deque()
    visited = [[0] * cols for _ in range(rows)]
    queue.append((start_x, start_y))
    visited[start_x][start_y] = 1
    
    while queue:
        current_x, current_y = queue.popleft()
        for dx, dy in ([-1, 0], [1, 0], [0, -1], [0, 1]):
            next_x, next_y = current_x + dx, current_y + dy
            if 0 <= next_x < rows and 0 <= next_y < cols and maps[next_x][next_y] == 1 and visited[next_x][next_y] == 0:
                queue.append((next_x, next_y))
                visited[next_x][next_y] = visited[current_x][current_y] + 1
    
    if visited[rows-1][cols-1] == 0:      
        return -1
    else:
        return visited[rows-1][cols-1]

def solution(maps):
    answer = bfs(0, 0, maps)
    return answer

입력 및 출력

maps = [[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]]

>> 11

3. 로직

---

1. bfs 함수는 출발점의 x 좌표 start_x, y 좌표 start_y, 그리고 맵 maps를 입력으로 받는다.

2. 맵의 행 수를 rows에 저장하고, 열 수를 cols에 저장한다.

3. 빈 큐인 queue와 방문 여부를 저장하는 2차원 리스트인 visited를 초기화한다. visited 리스트의 모든 요소를 0으로 초기화한다.

4. 출발점을 큐에 넣고, 해당 좌표를 방문한 것으로 표시한다. visited의 출발점 좌표를 1로 설정한다.

5. 큐가 비어있지 않은 동안 다음을 반복한다.

• 큐에서 현재 좌표 (current_x, current_y)를 꺼낸다.
• 상하좌우로 이동할 때의 변위를 나타내는 dx, dy 값을 순회한다. ([-1, 0], [1, 0], [0, -1], [0, 1])
• 현재 좌표에서 dx, dy를 더한 값이 맵 내에 있고, 해당 좌표가 벽이 아니며 방문하지 않은 경우,
  • 다음 좌표인 (next_x, next_y)를 큐에 추가한다.
  • 다음 좌표를 방문한 것으로 표시한다. visited[next_x]next_y]를 visited[current_x][current_y] + 1로 설정한다.

6. 도착점 좌표인 (rows-1, cols-1)이 방문되지 않았다면, 즉 도착점에 도달할 수 없는 경우 -1을 반환한다.
7. 그렇지 않으면 도착점에 도달하는 데 필요한 최소 이동 횟수인 visited[rows-1][cols-1]을 반환한다.