[프로그래머스] lv2 게임 맵 최단거리 / 파이썬, 고득점kit

문제설명 ==> 게임 맵 최단거리

캐릭터는 항상 (1,1) 위치에 존재하고 상대방 진영은 항상 n, m에 위치한다.

주의점!

• 이전 백준에서 풀던 문제와 차이점은 그래프 전체를 maps로 받기 때문에 가로의 길이와 세로의 길이를 내가 찾아주어야 한다.
• maps로 n과 m의 길이를 구한다.
• 상대방 진영에 닿을 수 없는 경우 -1을 출력한다.
• n과 m이 같을 수도 있고, 다를 수도 있다

 

상대방 진영까지의 최소 거리를 구하는 문제이므로 visited에 값을 추가하는 방식을 사용한다.

from collections import deque

def bfs(x, y, n, m, visited, maps):
    dx = [ 0, 0, -1, 1 ]
    dy = [ -1, 1, 0, 0 ]
    q = deque()
    q.append([x, y])
    visited[x][y] = 1
    while q:
        x, y = q.popleft()
        if x == n-1 and y == m-1:
            return visited[x][y]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1 and visited[nx][ny] == 0:
                visited[nx][ny] = visited[x][y] + 1
                q.append([nx, ny])
    return -1

def solution(maps):
    answer = 0
    n = len(maps)
    m = len(maps[0])
    visited = [ [0] * m for _ in range(n)]
    return bfs(0, 0, n, m, visited, maps)

 

bfs에서 n, m을 두 번 적어 중복이긴 하지만 가시성이 좋아서 또 넣었다.

n은 maps의 길이로 행의 개수, m은 maps[0]의 길이로 열의 개수를 의미한다. 

n과 m이 같을 수도 있고 다를 수도 있다. 하지만 입력받는 행끼리 열끼리의 길이는 늘 같기 때문에 위와 같이 적어서 길이를 표현해준다.