[Programmers/Python] 게임 맵 최단 거리 - BFS

문제

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

💭풀이 과정

1. 문제 조건

• input: 게임 맵 2차원리스트 n x m
  • 1 ≤ n, m ≤ 100인 자연수, n과 m 모두 1인 경우X
  • maps 값 0은 벽이 있고, 1은 벽이 없는 자리
  • 좌측 상단 (1, 1) 위치에서 시작, 상대 팀 진영 우측 하단 (n, m) 위치
• return: 상대 팀 진영까지 지나간 칸 개수 최솟값
  • 출발칸, 도착칸(상대 팀 진영 칸) 포함
  • 상대 팀의 진영 주위에 다 벽을 세워둔 경우, 상대 팀에 진영 도착할 수 없는 경우
  • : return -1

2. 알고리즘

• 최단 경로 (BFS)
• 변수
  • 방문여부 및 거리체크를 위한 2차원 배열(visited)
  • 큐
  • x, y 방향 배열 (dx, dy)

[과정]

• 큐에 출발점 (0, 0) 삽입, 해당 좌표 방문 처리
• 큐가 빌 때까지
  • 큐에서 좌표 pop, 동서남북 방향으로 움직인다.
    • 다음 좌표가 맵 범위 내에 있고, 벽이 아니며, 방문한 적이 없으면
      • 방문 처리, 이동거리 누적
      • 큐에 해당 좌표 삽입
• 상대팀 진영 좌표 (n, m)

🛠️코드

from collections import deque
def solution(maps):
    """
    게임 맵에 대해서 BFS 수행하는 함수
    Args:
        maps (list): n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열

    Returns:
        int: 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값
    """
    n = len(maps)       # 행
    m = len(maps[0])    # 열
    
    # 맵과 동일한 크기의 방문여부와 거리를 체크하기 위한 이중리스트
    visited = [[-1]*m for _ in range(n)] 
    
    # 큐 
    q = deque()
    
    q.append((0,0))     # 출발점 (0,0)부터 큐에 삽입 
    visited[0][0] = 1   # 출발점 (0,0)은 방문처리 
    
    # maps 기준으로 하,우,상,좌   
    dx = [0,1,0,-1]     
    dy = [1,0,-1,0]
    
    # 큐가 빌 때까지 반복
    while q:
        x,y = q.popleft()   # 선입선출 
        
        # 상우하좌 4 방향 탐색
        for k in range(4):
            # 상우하좌 위치 이동한 좌표값 
            nx, ny = x + dx[k], y + dy[k] 
            # 좌표값이 맵 내에 존재하고, 벽이 아니며, 방문한 적이 없다면 
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1 and visited[nx][ny] == -1:
                # 방문 처리 및 이동거리 누적 
                visited[nx][ny] = visited[x][y]+1
                # 큐에 삽입
                q.append((nx,ny))
                
    return visited[n-1][m-1]

 

여기서 중요한 부분은 visited 배열이다. 방문 여부와 동시에 거리를 체크하는 배열인데, 처음에 -1로 초기화를 해둔다. -1이면 방문하지 않은 칸이며, 방문한 칸이라면 누적된 거리 값이 저장된다.